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