oj.uz

Submission #63412

# Submission time Handle Problem Language Result Execution time Memory
63412 2018-08-01T18:18:23 Z ksun48 Homecoming (BOI18_homecoming) C++14
44 / 100
 1000 ms 47692 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]);
			}
			dp1[i] = max(dp1[i], dp0[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;
	}
	for(int i = 0; i < k; i++){
		ans = max(ans, test(n, k, a, b, i));
	}
	return ans;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 11 ms 492 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 4 ms 560 KB Output is correct
6 Execution timed out 1072 ms 1088 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 227 ms 41208 KB Output is correct
2 Correct 58 ms 41208 KB Output is correct
3 Correct 192 ms 47692 KB Output is correct
4 Correct 113 ms 47692 KB Output is correct
5 Correct 78 ms 47692 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 11 ms 492 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 4 ms 560 KB Output is correct
5 Correct 4 ms 560 KB Output is correct
6 Execution timed out 1072 ms 1088 KB Time limit exceeded
7 Halted 0 ms 0 KB -