Submission #1044056


Source Code Expand

#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"

using namespace std;

int N,K;
int num[100000];
long long int dp[100000][3];
long long int sum[100000];
int last[100000];
int kind[100000];
long long int box;
long long int ans;

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> num[i];
	}
	sum[0] = num[0];
	for (int i = 1; i < N; i++) {
		sum[i] = sum[i - 1] + num[i];
	}
	dp[0][0] = 0;
	last[0] = 0;
	kind[0] = 1;
	for (int i = 0; i < K; i++) {
		dp[0][1] += num[i];
	}
	dp[0][2] = 0;
	for (int i = 1; i <= N - K; i++) {
		dp[i][0] = dp[i - 1][0];
		last[i] = last[i - 1];
		kind[i] = kind[i - 1];
		if (dp[i][0] < dp[i - 1][1]) {
			dp[i][0] = dp[i - 1][1];
			last[i] = i - 1;
			kind[i] = 0;
		}
		if (dp[i][0] < dp[i - 1][2]) {
			dp[i][0] = dp[i - 1][2];
			last[i] = i - 1;
			kind[i] = 1;
		}

		dp[i][1] = dp[i - 1][1] + num[i];
		if (dp[i][1] < dp[i - 1][2] + sum[i + K - 1] - sum[i - 1])dp[i][1] = dp[i - 1][2] + sum[i + K - 1] - sum[i - 1];
		if (kind[i - 1] == 0) {
			if (dp[i][1] < dp[i - 1][0] + sum[i + K - 1] - sum[last[i] + K - 1])dp[i][1] = dp[i - 1][0] + sum[i + K - 1] - sum[last[i] + K - 1];
		}
		else {
			if (dp[i][1] < dp[i - 1][0] + sum[i + K - 1] - sum[i - 1])dp[i][1] = dp[i - 1][0] + sum[i + K - 1] - sum[i - 1];
		}

		dp[i][2] = dp[i - 1][2];
		if (dp[i][2] < dp[i - 1][1] + sum[i - 1] - sum[i + K - 2])dp[i][2] = dp[i - 1][1] + sum[i - 1] - sum[i + K - 2];
		if (kind[i - 1] == 0) {
			if (dp[i][2] < dp[i - 1][0] + sum[i - 1] - sum[last[i] + K - 1])dp[i][2] = dp[i - 1][0] + sum[i - 1] - sum[last[i] + K - 1];
		}
		else {
			if (dp[i][2] < dp[i - 1][0])dp[i][2] = dp[i - 1][0];
		}
		//cout << dp[i][0] << " " << dp[i][1] << " " << dp[i][2] << "\n";
	}
	ans = max({ dp[N - K][0],dp[N - K][1],dp[N - K][2] });
	cout << ans << "\n";
	return 0;
}

Submission Info

Submission Time
Task B - Contiguous Repainting
User olphe
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1994 Byte
Status WA
Exec Time 58 ms
Memory 4480 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 400
Status
AC × 3
WA × 1
AC × 13
WA × 13
Set Name Test Cases
Sample 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt
Case Name Status Exec Time Memory
0_00.txt AC 3 ms 256 KB
0_01.txt WA 3 ms 256 KB
0_02.txt AC 3 ms 256 KB
0_03.txt AC 3 ms 256 KB
1_00.txt AC 3 ms 256 KB
1_01.txt AC 3 ms 256 KB
1_02.txt AC 3 ms 256 KB
1_03.txt AC 28 ms 4480 KB
1_04.txt AC 54 ms 4480 KB
1_05.txt AC 58 ms 4480 KB
1_06.txt AC 52 ms 4480 KB
1_07.txt AC 56 ms 4480 KB
1_08.txt AC 50 ms 1408 KB
1_09.txt AC 49 ms 1408 KB
1_10.txt WA 49 ms 1408 KB
1_11.txt WA 51 ms 2432 KB
1_12.txt WA 51 ms 2560 KB
1_13.txt WA 50 ms 2432 KB
1_14.txt WA 48 ms 1536 KB
1_15.txt WA 52 ms 2944 KB
1_16.txt WA 52 ms 3328 KB
1_17.txt WA 50 ms 3584 KB
1_18.txt WA 51 ms 2432 KB
1_19.txt WA 48 ms 1920 KB
1_20.txt WA 51 ms 2176 KB
1_21.txt WA 50 ms 1792 KB