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.             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.     for i:=0 to Y do write(DP[i],'  '); writeln;
  80.     writeln(DP[Y]); { print result }
  81. end.
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
10 5 6
1 2 2 5 2
5 4 3 5 4
stdout
copy 
0  6  9  12  15  18  24  
24
https://ideone.com/WicPWu
language:
Pascal (fpc 3.0.4)
created:
5 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!