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.     DP[0] := 0;
  45.     for i:= 1 to Y do
  46.         DP[i] := 2000000000;
  47.  
  48.     u := 0;
  49.     for i:= 0 to D do
  50.     begin
  51.         for j:=1 to D do
  52.         begin
  53.             if (i+j <= Y) then
  54.             begin
  55.                 if (DP[i+j] >= DP[i] + cumulative[j]) then
  56.                     DP[i+j] := DP[i] + cumulative[j];
  57.                     writeln(DP[i+j]);
  58.             end;
  59.         end;
  60.         if ((i <= Y) and (DP[i] = cumulative[i])) then
  61.         begin
  62.             useful[u] := i;
  63.             u := u+1;
  64.         end;
  65.     end;
  66.  
  67.     for i:= D to Y do
  68.     begin
  69.         for k:=0 to u-1 do
  70.         begin
  71.             j := useful[k];
  72.             if (i+j <= Y) then
  73.             begin
  74.                 if (DP[i+j] >= DP[i] + cumulative[j]) then
  75.                     DP[i+j] := DP[i] + cumulative[j];
  76.             end;
  77.         end;
  78.     end;
  79.  
  80.     writeln(DP[Y]); { print result }
  81. end.
  82.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
100 3 1000
123 456 789
987 654 321
stdout
copy 
-764
25
1147
-1528
-739
383
-2292
-1503
-381
-3056
-2267
-1145
-764000
https://ideone.com/fYaBac
language:
Pascal (fpc 3.0.4)
created:
1 day 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!