test/aoj/0516.test.cpp

View this file on GitHub
Last update: 2022-12-23 01:30:30+09:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0516

Depends on

src/dp/cumulative_sum.hpp

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0516"

#include <bits/stdc++.h>
using namespace std;

#include "../../src/dp/cumulative_sum.hpp"

int main() {
  while (true) {
    int n, k;
    cin >> n >> k;
    if (n == 0 && k == 0) {
      break;
    }
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
    }
    CumulativeSum<long long> cs(a);
    long long ans = numeric_limits<long long>::min();
    for (int i = 0; i + k <= n; ++i) {
      ans = max(ans, cs.sum(i, i + k));
    }
    cout << ans << endl;
  }
}

#line 1 "test/aoj/0516.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0516"

#include <bits/stdc++.h>
using namespace std;

#line 2 "src/dp/cumulative_sum.hpp"

#line 4 "src/dp/cumulative_sum.hpp"
using namespace std;

template <typename T> struct CumulativeSum {
private:
  vector<T> s;

public:
  CumulativeSum(const vector<T> &nums) {
    int n = nums.size();
    s.resize(n + 1, 0);
    for (int i = 0; i < n; ++i) {
      s[i + 1] = s[i] + nums[i];
    }
  }

  // [l, r), l and r is 0-indexed.
  T sum(int l, int r) { return s[r] - s[l]; }
};
#line 7 "test/aoj/0516.test.cpp"

int main() {
  while (true) {
    int n, k;
    cin >> n >> k;
    if (n == 0 && k == 0) {
      break;
    }
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) {
      cin >> a[i];
    }
    CumulativeSum<long long> cs(a);
    long long ans = numeric_limits<long long>::min();
    for (int i = 0; i + k <= n; ++i) {
      ans = max(ans, cs.sum(i, i + k));
    }
    cout << ans << endl;
  }
}