oj.uz

Submission #151957

# Submission time Handle Problem Language Result Execution time Memory
151957 2019-09-05T16:08:43 Z atoiz Homecoming (BOI18_homecoming) C++14
44 / 100
 136 ms 55528 KB 
#include "homecoming.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

long long solve(int N, int K, int *A, int *B)
{
	if (K == 1) {
		long long ans = 0;
		for (int i = 0; i < N; ++i) ans += max(0, A[i] - B[i]);
		return ans;
	}

	static const long long INF = 1e17;

	long long ans = accumulate(A, A + N, 0) - accumulate(B, B + N, 0);
	if (ans < 0) ans = 0;

	vector<long long> total(N * 2, 0); total[0] = B[0];
	for (int i = 1; i < N * 2; ++i) total[i] = total[i - 1] + B[i % N];

	vector<vector<long long>> dp(2);

	dp[0].assign(N + 1, 0); dp[1].assign(N + 1, -INF);
	dp[1][0] = 0;
	for (int i = 1; i <= N; ++i) {
		dp[1][i] = dp[1][i - 1];
		if (i - K + 1 >= 0) dp[1][i] = max(dp[1][i], dp[0][i - K + 1] - total[i - 1] + (i - K >= 0 ? total[i - 1 - K + 1] : 0));
		dp[0][i] = max(dp[0][i - 1] + A[i - 1] - B[i - 1], dp[1][i]);
		ans = max(ans, dp[0][i] - total[i + K - 2] + total[i - 1]);
	}
	ans = max(ans, *max_element(dp[1].begin(), dp[1].end()));

	dp[0].assign(N + 1, 0); dp[1].assign(N + 1, -INF);
	dp[0][1] = A[0] - B[0];
	for (int i = 2; i <= N; ++i) {
		dp[1][i] = dp[1][i - 1];
		if (i - K + 1 >= 0) dp[1][i] = max(dp[1][i], dp[0][i - K + 1] - total[i - 1] + (i - K >= 0 ? total[i - 1 - K + 1] : 0));
		dp[0][i] = max(dp[0][i - 1] + A[i - 1] - B[i - 1], dp[1][i]);
	}
	ans = max(ans, *max_element(dp[1].begin(), dp[1].end()));
	ans = max(ans, dp[0][N]);

	return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Incorrect 3 ms 376 KB Output isn't correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 29304 KB Output is correct
2 Correct 5 ms 888 KB Output is correct
3 Correct 136 ms 55528 KB Output is correct
4 Correct 4 ms 1400 KB Output is correct
5 Correct 12 ms 2936 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Incorrect 3 ms 376 KB Output isn't correct