Advertisement
Guest User

Untitled

a guest
Oct 25th, 2014
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     int n, k;
  10.     scanf("%d%d", &n, &k);
  11.     vector <int> a(n);
  12.     vector <int> d(n, 0);
  13.     int sum = 0;
  14.     for (int i = 0; i < n; ++i) {
  15.         scanf("%d", &a[i]);
  16.         sum += a[i];
  17.         if (i>= k) {
  18.             sum -= a[i - k];
  19.         }
  20.         d[i] = sum;
  21.     }
  22.     for (int i = 1; i < n; ++i) {
  23.         d[i] = max(d[i], d[i - 1]);
  24.     }
  25.     vector <int> d1(n, 0);
  26.     sum = 0;
  27.     for (int i = n - 1; i >= 0; --i) {
  28.         sum += a[i];
  29.         if (i < n - k) {
  30.             sum -= a[i + k];
  31.         }
  32.         d1[i] = sum;
  33.     }
  34.     for (int i = n - 2; i >= 0; --i) {
  35.         d1[i] = max(d1[i], d1[i + 1]);
  36.     }
  37.     int ans = 0;
  38.     for (int i = 0; i < n - 1; ++i) {
  39.         ans = max(ans, d[i] + d1[i + 1]);
  40.     }
  41.     printf("%d", ans);
  42. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement