fork download
copy 
  1. const fi='SOFTWARE.inp'; fo='SOFTWARE.out';
  2.      MAXN = 105;
  3.      SUMMAXVAL = 3000005;
  4. var
  5. 	sump,sumc,n,SUMMAX:longint;
  6. 	p,c:array[0..MAXN] of integer;
  7. 	F:array[0..SUMMAXVAL] of longint;
  8. 	Trace:array[0..MAXN,0..SUMMAXVAL] of byte;
  9. procedure Inp;
  10. var i,j:longint;
  11. begin
  12. 	read(n);
  13. 	for i:=1 to n do begin
  14. 		read(p[i]);
  15.       inc(sump,p[i]);
  16. 	end;
  17.    for i:=1 to n do begin
  18. 		read(c[i]);
  19. 		inc(sumc,c[i]);
  20. 	end;
  21. 	if (sump>sumc) then SUMMAX:=sump else SUMMAX:=sumc;
  22. end;
  23.  
  24. procedure Calc(t:longint);
  25. var i,j:longint;
  26. begin
  27. 	for i:=1 to n do
  28. 	  for j:=t downto 1 do begin
  29. 		  if F[j-1]>F[j] then begin
  30. 				F[j]:=F[j-1];
  31. 				Trace[i][j]:=1;
  32. 			end else begin
  33. 				Trace[i][j]:=2;
  34. 			end;
  35. 		  if (j-c[i]>=0) and (F[j-c[i]] + p[i]>F[j]) then begin
  36. 				F[j] := F[j-c[i]] + p[i];
  37. 				Trace[i][j]:=3;
  38. 			end;
  39. 		end;
  40. end;
  41.  
  42. procedure Main;
  43. var ans,i,j,l,r,k:longint;
  44.     codec:array[0..MAXN] of boolean;
  45. begin
  46. 	Calc(SUMMAX);
  47. 	for i:=1 to SUMMAX do
  48. 	  if (sump-F[i]<=i) then break;
  49. 	writeln(i);
  50. 	j:=i; i:=n;
  51. 	fillchar(codec,sizeof(codec),false);
  52. 	while (i<>0) and (j<>0) do begin
  53. 		if (Trace[i][j]=1) then dec(j)
  54. 		else if (Trace[i][j]=2) then dec(i)
  55. 		else begin
  56. 			codec[i]:=true;
  57.          dec(j,c[i]); dec(i);
  58. 		end;
  59. 	end;
  60. 	for i:=1 to n do
  61. 	 if (codec[i]=false) then write(i,' ');
  62. 	 writeln;
  63. 	for i:=1 to n do if (codec[i]) then write(i,' ');
  64. end;
  65.  
  66. begin
  67.  
  68. 	Inp;
  69. 	Main;
  70. end.
  71.  
Success #stdin #stdout 0s 322560KB
comments (?)
stdin
copy 
6
10 100 30 50 50 80
100 30 40 40 60 90
stdout
copy 
130
1 3 6 
2 4 5
https://ideone.com/r2Ucqt
language:
Pascal (fpc 3.0.4)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!