Submission #12545419


Source Code Expand

Copy
#include <memory.h>

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

#define mod 1000000007

const long long int INIT = (long long int)mod * -20000;

int n, k;
long long int b[200010] = {};
long long int result[200010][2];

long long int solve(int x, bool f) {
	if (x == n) return 0;
	if (result[x][f] != INIT) return result[x][f];

	if (f) {
		result[x][f] = max(solve(x + 1, true), solve(x, false));
	} else {
		result[x][f] = solve(x + 1, false) + b[x];
		if (x + k <= n) result[x][f] = max(result[x][f], solve(x + k, true));
	}
	// cout << x << " " << f << " " << result[x][f] << endl;
	return result[x][f];
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> b[i];
		result[i][0] = result[i][1] = INIT;
	}

	cout << solve(0, false) << endl;
}

Submission Info

Submission Time
Task B - Neutralize
User maple
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1118 Byte
Status
Exec Time 97 ms
Memory 11136 KB

Judge Result

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 2 ms 2304 KB
a02 2 ms 2304 KB
a03 2 ms 2304 KB
a04 2 ms 2304 KB
b05 2 ms 2304 KB
b06 2 ms 2304 KB
b07 10 ms 3200 KB
b08 97 ms 11136 KB
b09 97 ms 11136 KB
b10 95 ms 11136 KB
b11 95 ms 11136 KB
b12 2 ms 2304 KB
b13 69 ms 11136 KB
b14 69 ms 11136 KB
b15 90 ms 11136 KB
b16 91 ms 11136 KB
b17 92 ms 11136 KB
b18 93 ms 11136 KB
b19 94 ms 11136 KB
b20 72 ms 10496 KB
b21 60 ms 11136 KB
b22 76 ms 11136 KB
b23 87 ms 11136 KB
b24 51 ms 9472 KB
b25 70 ms 11136 KB
b26 77 ms 11008 KB
b27 53 ms 11136 KB
b28 62 ms 11008 KB
b29 56 ms 11136 KB
b30 46 ms 7424 KB
b31 73 ms 11136 KB
b32 59 ms 10752 KB
b33 49 ms 9728 KB
b34 67 ms 10624 KB
b35 89 ms 11136 KB
b36 90 ms 11136 KB
b37 91 ms 11136 KB
b38 90 ms 11136 KB
b39 95 ms 11136 KB
b40 90 ms 11136 KB
b41 90 ms 11136 KB
b42 91 ms 11136 KB
b43 90 ms 11136 KB
b44 90 ms 11136 KB