oj.uz

Submission #63457

# Submission time Handle Problem Language Result Execution time Memory
63457 2018-08-01T21:12:59 Z ksun48 Homecoming (BOI18_homecoming) C++14
13 / 100
 246 ms 47868 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

const LL reallybad = -10000000000000000LL;

LL test(int n, int k, vector<LL> a, vector<LL> b, int x){
	LL ans = reallybad;
	vector<LL> newa;
	vector<LL> newb;
	vector<LL> bpsums(1,0);
	for(int i = 0; i < n; i++){
		newa.push_back(a[(i+x) % n]);
		newb.push_back(b[(i+x) % n]);
	}
	for(int i = 0; i < n; i++){
		bpsums.push_back(bpsums[i] + newb[i]);
	}
	for(int y = 0; y < 2; y++){
		vector<LL> dp0(n+1, reallybad);
		vector<LL> dp1(n+1, reallybad);
		if(y == 0) dp0[0] = 0;
		if(y == 1) dp1[0] = 0;

		for(int i = 0; i <= n; i++){
			dp1[i] = max(dp1[i], dp0[i]);
			if(i + 1 <= n){
				dp0[i+1] = max(dp0[i+1], dp0[i]);
				dp1[i+1] = max(dp1[i+1], dp1[i] + newa[i] - newb[i]);
			}
			if(i + k <= n){
				dp0[i+k] = max(dp0[i+k], dp1[i] - bpsums[i+k] + bpsums[i]);
			}
		}

		if(y == 0) ans = max(ans, dp0[n]);
		if(y == 1) ans = max(ans, dp1[n]);
	}
	return ans;
}

long long solve(int N, int K, int *A, int *B){
	int n = N;
	int k = K;
	k--;
	vector<LL> a, b;
	for(int i = 0; i < n; i++){
		a.push_back(A[i]);
		b.push_back(B[i]);
	}
	LL ans = 0;
	if(k == 0){
		for(int i = 0; i < n; i++){
			if(a[i] >= b[i]){
				ans += a[i] - b[i];
			}
		}
		return ans;
	}
	LL best = 0;
	LL bestidx = 0;
	LL sum = 0;
	for(int i = 0; i < k; i++){
		sum += a[i] - b[i];
		if(sum > best){
			best = sum;
			bestidx = i;
		}
	}
	ans = max(ans, test(n, k, a, b, 0));
	//ans = max(ans, test(n, k, a, b, k-1));
	ans = max(ans, test(n, k, a, b, bestidx));
	return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 444 KB Output is correct
4 Correct 2 ms 680 KB Output is correct
5 Correct 2 ms 680 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 444 KB Output is correct
4 Correct 2 ms 680 KB Output is correct
5 Correct 2 ms 680 KB Output is correct
6 Correct 4 ms 964 KB Output is correct
7 Correct 4 ms 1056 KB Output is correct
8 Correct 3 ms 1056 KB Output is correct
9 Correct 4 ms 1056 KB Output is correct
10 Incorrect 6 ms 1056 KB Output isn't correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 41320 KB Output is correct
2 Correct 9 ms 41320 KB Output is correct
3 Correct 246 ms 47868 KB Output is correct
4 Correct 8 ms 47868 KB Output is correct
5 Incorrect 23 ms 47868 KB Output isn't correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 248 KB Output is correct
2 Correct 2 ms 356 KB Output is correct
3 Correct 3 ms 444 KB Output is correct
4 Correct 2 ms 680 KB Output is correct
5 Correct 2 ms 680 KB Output is correct
6 Correct 4 ms 964 KB Output is correct
7 Correct 4 ms 1056 KB Output is correct
8 Correct 3 ms 1056 KB Output is correct
9 Correct 4 ms 1056 KB Output is correct
10 Incorrect 6 ms 1056 KB Output isn't correct