Advertisement
Guest User

Untitled

a guest
Aug 16th, 2011
237
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Delphi 0.81 KB | None | 0 0
  1. program solution;
  2.  
  3. {$APPTYPE CONSOLE}
  4. {MODE DELPHI}
  5. {$MAXSTACKSIZE 1000000000}
  6. {O-,R+,Q+}
  7. {$O+,R-,Q-}
  8.  
  9. uses
  10.   SysUtils,
  11.   Math;
  12.  
  13. const
  14.   inf = round(1e9);
  15.  
  16. var
  17.   n, m, k, ans, i, j : integer;
  18.   a, sum, d, dd : array[0..30001] of integer;
  19.  
  20. begin
  21.   //assign(input, 'input.txt'); reset(input);
  22.   //assign(output, 'output.txt'); rewrite(output);
  23.   read(n, m, k);
  24.   for i := 1 to n do
  25.     read(a[i]);
  26.   for i := 1 to n do
  27.     sum[i] := sum[i - 1] + a[i];
  28.   ans := -inf;
  29.   for i := 1 to m do begin
  30.     for j := 0 to n do
  31.       dd[j] := -inf;
  32.     for j := 1 to n do begin
  33.       dd[j] := max(dd[j], dd[j - 1]);
  34.       dd[j] := max(dd[j], d[max(j - k, 0)] + sum[j] - sum[max(j - k, 0)]);
  35.     end;
  36.     for j := 0 to n do
  37.       d[j] := dd[j];
  38.     ans := max(ans, d[n]);
  39.   end;
  40.   writeln(ans);
  41. end.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement