oj.uz

Submission #254650

# Submission time Handle Problem Language Result Execution time Memory
254650 2020-07-30T11:52:38 Z Saboon Homecoming (BOI18_homecoming) C++14
44 / 100
 1000 ms 78712 KB 
#include<bits/stdc++.h>
#include"homecoming.h"
using namespace std;
typedef long long ll;
const int maxn = 2e6 + 20;
const ll inf = 1e18 + 7;

ll dp[maxn][2];
ll par[2*maxn];
int N;

ll getsum(int l, int r){
	if (l < 0)
		l += N, r += N;
	return par[r+1] - par[l];
}

ll solve(int n, int k, int* a, int* b){
	N = n;
	for (int i = 1; i <= n; i++)
		par[i] = par[i-1] + b[i-1];
	for (int i = n+1; i <= 2*n; i++)
		par[i] = par[i-1] + b[i-n-1];
	dp[0][0] = 0, dp[0][1] = -inf;
	for (int i = 1; i < n; i++){
		dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
		if (i-k+1 > 0)
			dp[i][1] = max(dp[i-k][0] + a[i-k+1] - getsum(i-k+1, i), dp[i-1][1] + a[i-k+1] - b[i]);
		else
			dp[i][1] = -inf;
	}
	ll answer = max(dp[n-1][0],dp[n-1][1]);
	ll tot = 0;
	for (int i = 0; i < n; i++)
		tot += a[i] - b[i];
	answer = max(answer, tot);
	for (int i = 1; i <= n; i++)
		par[i] = par[i-1] + a[i-1];
	for (int i = n+1; i <= 2*n; i++)
		par[i] = par[i-1] + a[i-n-1];
	memset(dp, -63, sizeof dp);
	dp[0][0] = -inf, dp[0][1] = 0;
	for (int i = 1; i < n; i++){
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]);
		dp[i][0] = max(dp[i-1][0] + b[i] - a[i], dp[i-1][1] + b[i] - getsum(i-k+1, i));
	}
	answer = max(answer, tot + max(dp[n-1][0],dp[n-1][1]));
	return answer;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31616 KB Output is correct
2 Correct 22 ms 31616 KB Output is correct
3 Correct 75 ms 31616 KB Output is correct
4 Correct 15 ms 31616 KB Output is correct
5 Correct 27 ms 31616 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31616 KB Output is correct
2 Correct 22 ms 31616 KB Output is correct
3 Correct 75 ms 31616 KB Output is correct
4 Correct 15 ms 31616 KB Output is correct
5 Correct 27 ms 31616 KB Output is correct
6 Correct 17 ms 31744 KB Output is correct
7 Correct 17 ms 31744 KB Output is correct
8 Correct 32 ms 31740 KB Output is correct
9 Correct 16 ms 31872 KB Output is correct
10 Execution timed out 1089 ms 31744 KB Time limit exceeded

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 43384 KB Output is correct
2 Correct 123 ms 31616 KB Output is correct
3 Correct 177 ms 78712 KB Output is correct
4 Correct 19 ms 32152 KB Output is correct
5 Correct 459 ms 32176 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 31616 KB Output is correct
2 Correct 22 ms 31616 KB Output is correct
3 Correct 75 ms 31616 KB Output is correct
4 Correct 15 ms 31616 KB Output is correct
5 Correct 27 ms 31616 KB Output is correct
6 Correct 17 ms 31744 KB Output is correct
7 Correct 17 ms 31744 KB Output is correct
8 Correct 32 ms 31740 KB Output is correct
9 Correct 16 ms 31872 KB Output is correct
10 Execution timed out 1089 ms 31744 KB Time limit exceeded