Submission #3331250


Source Code Expand

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

long long k, n;
long long b[200005] = {0};
long long dp[200005] = {0};

long long solve();

int main() {
  cin >> n >> k;
  for(int i = 0; i < n; ++i) cin >> b[i];
  cout << solve() << endl;
  return 0;
}

long long solve() {
  dp[0] = b[0];
  for(int i = 1; i < k; ++i) dp[i] = dp[i - 1] + b[i];
  dp[k - 1] = max(0LL, dp[k - 1]);
  for(int i = 0; i < n; ++i) {
    if(i != 0) dp[i] = max(dp[i], dp[i - 1] + b[i]);
    if(i + k < n) dp[i + k] = max(dp[i + k], dp[i]);
    if(i + k + 1 < n) dp[i + k + 1] = dp[i + k];
  }
  return dp[n - 1];
}

Submission Info

Submission Time
Task B - Neutralize
User m_tsubasa
Language C++14 (GCC 5.4.1)
Score 400
Code Size 616 Byte
Status
Exec Time 94 ms
Memory 3328 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 a01, a02, a03, a04
All 400 / 400 a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44
Case Name Status Exec Time Memory
a01 1 ms 256 KB
a02 1 ms 256 KB
a03 1 ms 256 KB
a04 1 ms 256 KB
b05 1 ms 256 KB
b06 1 ms 256 KB
b07 10 ms 512 KB
b08 94 ms 3328 KB
b09 92 ms 3328 KB
b10 92 ms 3328 KB
b11 92 ms 3328 KB
b12 1 ms 256 KB
b13 65 ms 3328 KB
b14 64 ms 3328 KB
b15 85 ms 3328 KB
b16 86 ms 3328 KB
b17 87 ms 3328 KB
b18 88 ms 3328 KB
b19 89 ms 3328 KB
b20 67 ms 3072 KB
b21 56 ms 3328 KB
b22 72 ms 3328 KB
b23 82 ms 3328 KB
b24 47 ms 2688 KB
b25 64 ms 3328 KB
b26 72 ms 3328 KB
b27 49 ms 3328 KB
b28 57 ms 3328 KB
b29 51 ms 3328 KB
b30 43 ms 1920 KB
b31 68 ms 3328 KB
b32 53 ms 3200 KB
b33 45 ms 2816 KB
b34 62 ms 3072 KB
b35 85 ms 3328 KB
b36 85 ms 3328 KB
b37 85 ms 3328 KB
b38 85 ms 3328 KB
b39 85 ms 3328 KB
b40 85 ms 3328 KB
b41 85 ms 3328 KB
b42 86 ms 3328 KB
b43 85 ms 3328 KB
b44 85 ms 3328 KB