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.             end;
  58.         end;
  59.         if ((i <= Y) and (DP[i] = cumulative[i])) then
  60.         begin
  61.             useful[u] := i;
  62.             u := u+1;
  63.         end;
  64.     end;
  65.  
  66.     for i:= D to Y do
  67.     begin
  68.         for k:=0 to u-1 do
  69.         begin
  70.             j := useful[k];
  71.             if (i+j <= Y) then
  72.             begin
  73.                 if (DP[i+j] >= DP[i] + cumulative[j]) then
  74.                     DP[i+j] := DP[i] + cumulative[j];
  75.             end;
  76.         end;
  77.     end;
  78.  
  79.     writeln(DP[Y]); { print result }
  80. end.
  81.  
Success #stdin #stdout 0s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/bz6tsV
language:
Pascal (fpc 3.0.4)
created:
19 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!