oj.uz

Submission #63423

# Submission time Handle Problem Language Result Execution time Memory
63423 2018-08-01T18:47:19 Z jangwonyoung Homecoming (BOI18_homecoming) C++14
0 / 100
 272 ms 110228 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-1)]+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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Incorrect 2 ms 592 KB Output isn't correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Incorrect 2 ms 592 KB Output isn't correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 28068 KB Output is correct
2 Correct 7 ms 28068 KB Output is correct
3 Incorrect 272 ms 110228 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 2 ms 488 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Incorrect 2 ms 592 KB Output isn't correct