oj.uz

Submission #254266

# Submission time Handle Problem Language Result Execution time Memory
254266 2020-07-29T15:56:40 Z amoo_safar Homecoming (BOI18_homecoming) C++14
100 / 100
 154 ms 47388 KB 
// Null
#include <bits/stdc++.h>

#ifndef safar
#include "homecoming.h"
#endif

using namespace std;

typedef long long ll;

const int NN = 2e6 + 10;
const ll Inf = 1e16;

ll dp[2][NN];

ll solve(int n, int k, int *A, int *B){

	ll ans = 0;
	ll S2 = 0;
	for(int i = 0; i < n; i++) S2 += A[i];
	for(int i = 0; i < n; i++) S2 -= B[i];

	ans = max(ans, S2);
	if(n == k){
		return ans;
	}

	fill(dp[0], dp[0] + n + 1, -Inf);
	fill(dp[1], dp[1] + n + 1, -Inf);
	
	dp[0][0] = 0;
	ll Sm = B[0];
	for(int i = 1; i < n; i++){
		Sm += B[i];
		dp[0][i] = max(dp[0][i - 1], dp[1][i - 1]);
		if(i >= k){
			Sm -= B[i - k];
			dp[1][i] = max(dp[1][i - 1] - B[i] + A[i - k + 1], dp[0][i-k] + A[i - k + 1] - Sm);
		}
	}
	ans = max({ans, dp[0][n - 1], dp[1][n - 1]});

	fill(dp[0], dp[0] + n + 1, -Inf);
	fill(dp[1], dp[1] + n + 1, -Inf);
	dp[1][0] = 0;

	Sm = 0;
	for(int i = 0; i < k; i++) Sm += A[(n - i) % n];

	for(int i = 1; i < n; i++){
		Sm += A[i];
		Sm -= A[(i - k + n) % n];

		dp[1][i] = max(dp[0][i - 1], dp[1][i - 1]);
		
		dp[0][i] = max(dp[0][i - 1] + B[i] - A[i], dp[1][i - 1] + B[i] - Sm);
	}
	S2 = 0;
	for(int i = 0; i < n; i++) S2 += ((ll)A[i]) - B[i];

	ans = max(ans, S2 + max(dp[0][n - 1], dp[1][n - 1]));
	ans = max(ans, S2);
	return ans;
}

#ifdef safar
int Ai[3] = {0, 0, 1}, Bi[3] = {0, 2, 0};
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cout << solve(3, 2, Ai, Bi) << '\n';
	return 0;
}
#endif

Subtask #1
13.0 / 13.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 12152 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 147 ms 47352 KB Output is correct
4 Correct 2 ms 1152 KB Output is correct
5 Correct 14 ms 1664 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 512 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 41 ms 12152 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 147 ms 47352 KB Output is correct
14 Correct 2 ms 1152 KB Output is correct
15 Correct 14 ms 1664 KB Output is correct
16 Correct 154 ms 47388 KB Output is correct
17 Correct 68 ms 6520 KB Output is correct
18 Correct 134 ms 3356 KB Output is correct
19 Correct 118 ms 23892 KB Output is correct
20 Correct 118 ms 47352 KB Output is correct
21 Correct 121 ms 23924 KB Output is correct