oj.uz

Submission #63431

# Submission time Handle Problem Language Result Execution time Memory
63431 2018-08-01T18:55:56 Z jangwonyoung Homecoming (BOI18_homecoming) C++14
100 / 100
 270 ms 110276 KB 
#include<iostream>
#include "homecoming.h"
using namespace std;
typedef long long ll;
ll pref[4000001];
ll C[4000001];
ll dp[2000001][2][2];
ll solve(int N,int K,int *A,int *B){
	pref[0]=0;
	for(int i=1; i<=2*N ;i++){
		pref[i]=pref[i-1]+B[(i-1)%N];
	}
	dp[0][0][0]=0;
	dp[0][1][1]=A[0]-pref[K];
	dp[0][1][0]=dp[0][0][1]=-1e18;
	for(int i=1; i<N ;i++){
		int j=(i+K-1);
		dp[i][0][0]=max(dp[i-1][0][0],dp[i-1][0][1]);
		dp[i][0][1]=max(dp[i-1][0][0]-pref[i+K]+pref[i],dp[i-1][0][1]-B[j%N])+A[i];
		dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][1][1]);
		dp[i][1][1]=max(dp[i-1][1][0]-pref[min(i+K,N)]+pref[i],dp[i-1][1][1]-(j>=N?0:B[j]))+A[i];
	}
	return max(max(dp[N-1][0][0],dp[N-1][0][1]),max(dp[N-1][1][0],dp[N-1][1][1]));
}

Subtask #1
13.0 / 13.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 580 KB Output is correct
3 Correct 3 ms 580 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 2 ms 580 KB Output is correct
6 Correct 3 ms 700 KB Output is correct
7 Correct 3 ms 744 KB Output is correct
8 Correct 3 ms 744 KB Output is correct
9 Correct 3 ms 792 KB Output is correct
10 Correct 4 ms 792 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 27900 KB Output is correct
2 Correct 6 ms 27900 KB Output is correct
3 Correct 235 ms 110196 KB Output is correct
4 Correct 5 ms 110196 KB Output is correct
5 Correct 14 ms 110196 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 580 KB Output is correct
3 Correct 3 ms 580 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 2 ms 580 KB Output is correct
6 Correct 3 ms 700 KB Output is correct
7 Correct 3 ms 744 KB Output is correct
8 Correct 3 ms 744 KB Output is correct
9 Correct 3 ms 792 KB Output is correct
10 Correct 4 ms 792 KB Output is correct
11 Correct 86 ms 27900 KB Output is correct
12 Correct 6 ms 27900 KB Output is correct
13 Correct 235 ms 110196 KB Output is correct
14 Correct 5 ms 110196 KB Output is correct
15 Correct 14 ms 110196 KB Output is correct
16 Correct 270 ms 110276 KB Output is correct
17 Correct 121 ms 110276 KB Output is correct
18 Correct 159 ms 110276 KB Output is correct
19 Correct 169 ms 110276 KB Output is correct
20 Correct 193 ms 110276 KB Output is correct
21 Correct 168 ms 110276 KB Output is correct