oj.uz

Submission #63461

# Submission time Handle Problem Language Result Execution time Memory
63461 2018-08-01T21:15:09 Z ksun48 Homecoming (BOI18_homecoming) C++14
100 / 100
 777 ms 168636 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 376 KB Output is correct
2 Correct 2 ms 576 KB Output is correct
3 Correct 3 ms 576 KB Output is correct
4 Correct 4 ms 576 KB Output is correct
5 Correct 3 ms 576 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 576 KB Output is correct
3 Correct 3 ms 576 KB Output is correct
4 Correct 4 ms 576 KB Output is correct
5 Correct 3 ms 576 KB Output is correct
6 Correct 4 ms 1032 KB Output is correct
7 Correct 4 ms 1032 KB Output is correct
8 Correct 4 ms 1032 KB Output is correct
9 Correct 5 ms 1032 KB Output is correct
10 Correct 6 ms 1032 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 41308 KB Output is correct
2 Correct 8 ms 41308 KB Output is correct
3 Correct 210 ms 47732 KB Output is correct
4 Correct 9 ms 47732 KB Output is correct
5 Correct 28 ms 47732 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 576 KB Output is correct
3 Correct 3 ms 576 KB Output is correct
4 Correct 4 ms 576 KB Output is correct
5 Correct 3 ms 576 KB Output is correct
6 Correct 4 ms 1032 KB Output is correct
7 Correct 4 ms 1032 KB Output is correct
8 Correct 4 ms 1032 KB Output is correct
9 Correct 5 ms 1032 KB Output is correct
10 Correct 6 ms 1032 KB Output is correct
11 Correct 182 ms 41308 KB Output is correct
12 Correct 8 ms 41308 KB Output is correct
13 Correct 210 ms 47732 KB Output is correct
14 Correct 9 ms 47732 KB Output is correct
15 Correct 28 ms 47732 KB Output is correct
16 Correct 777 ms 163488 KB Output is correct
17 Correct 306 ms 163488 KB Output is correct
18 Correct 477 ms 163488 KB Output is correct
19 Correct 637 ms 163488 KB Output is correct
20 Correct 677 ms 168636 KB Output is correct
21 Correct 707 ms 168636 KB Output is correct