fork download
copy 
  1. { NOTE: it is recommended to use this even if you don't understand the following code. }
  2.  
  3. { constraints }
  4. const
  5.     MAXD = 1000;
  6.     MAXY = 1000000;
  7.  
  8. { input data }
  9. var
  10.     C, D, Y, i  : longint;
  11.     // Warning! M and P are 1-based
  12.     M, P        : array[1..MAXD] of longint;
  13.     cumulative  : array[1..MAXD] of longint;
  14.     DP : array[0..MAXY] of longint;
  15.     j, k, u : longint;
  16.     useful : array[0..MAXD] of longint;
  17.  
  18. begin
  19. {
  20.     uncomment the following lines if you want to read/write from files
  21.     assign(input,  'input.txt');  reset(input);
  22.     assign(output, 'output.txt'); rewrite(output);
  23. }
  24.  
  25.     readln(C, D, Y);
  26.     // Warning! M and P are 1-based
  27.     for i:=1 to D do
  28.         read(M[i]);
  29.     readln();
  30.     for i:=1 to D do
  31.         read(P[i]);
  32.     readln();
  33.  
  34.     cumulative[1] := M[1];
  35.     for i:=2 to D do
  36.         cumulative[i] := cumulative[i-1] + M[i];
  37.  
  38.     for i:=1 to D do
  39.     begin
  40.         cumulative[i] := cumulative[i] + C;
  41.         cumulative[i] := cumulative[i] - P[i];
  42.     end;
  43.  
  44.     for i:=1 to D   do write (cumulative[i],'  '); writeln;
  45.  
  46.     DP[0] := 0;
  47.     for i:= 1 to Y do
  48.         DP[i] := 2000000000;
  49.  
  50.     u := 0;
  51.     for i:= 0 to D do
  52.     begin
  53.         for j:=1 to D do
  54.         begin
  55.             if (i+j <= Y) then
  56.             begin
  57.                 if (DP[i+j] >= DP[i] + cumulative[j]) then
  58.                     DP[i+j] := DP[i] + cumulative[j];
  59.             end;
  60.         end;
  61.  
  62.  
  63.         if ((i <= Y) and (DP[i] = cumulative[i])) then
  64.         begin
  65.             useful[u] := i;
  66.             u := u+1;
  67.         end;
  68.     end;
  69.    for i:= 0 to D do write( DP[i], ' '); writeln;  
  70.    for i:=0 to 5 do write(useful[i],' '); writeln;
  71.     for i:= D to Y do
  72.     begin
  73.         for k:=0 to u-1 do
  74.         begin
  75.             j := useful[k];
  76.             if (i+j <= Y) then
  77.             begin
  78.                 if (DP[i+j] >= DP[i] + cumulative[j]) then
  79.                     DP[i+j] := DP[i] + cumulative[j];
  80.             end;
  81.         end;
  82.     end;
  83.  for i:=1 to y   do write (cumulative[i],'  '); writeln;
  84.     writeln(DP[Y]); { print result }
  85. end.
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
10 5 8
1 2 2 5 2
5 4 3 5 4
stdout
copy 
6  9  12  15  18  
0 6 9 12 15 18 
0 1 2 3 4 5 
6  9  12  15  18  0  0  0  
30
https://ideone.com/fzTGsA
language:
Pascal (fpc 3.0.4)
created:
6 hours 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!