oj.uz

Submission #152136

# Submission time Handle Problem Language Result Execution time Memory
152136 2019-09-06T15:08:36 Z HungAnhGoldIBO2020 Homecoming (BOI18_homecoming) C++14
100 / 100
 210 ms 98376 KB 
#include "homecoming.h"
#include<iostream>
#include<vector>
using namespace std;
const int n=2e6+2;
const long long inf=1e18+2;
long long dp[n][2][2],sum[n];			//co chon khong , loai nao
long long solve(int N,int K,int* A,int* B){
	int i;
	for(i=0;i<N;i++){
		sum[i]=B[i];
		if(i){
			sum[i]+=sum[i-1];
		}
		dp[i][0][0]=-inf;
		dp[i][1][0]=-inf;
		dp[i][0][1]=-inf;
		dp[i][1][1]=-inf;
	}
	dp[0][0][0]=0;
	dp[0][1][1]=A[0]-sum[K-1];
//	cout<<dp[0][1][1]<<endl;
	for(i=1;i<N;i++){
		dp[i][0][0]=max(dp[i-1][0][0],dp[i-1][1][0]);
		dp[i][0][1]=max(dp[i-1][0][1],dp[i-1][1][1]);
		if(i+K-1<N){
			dp[i][1][0]=max(dp[i-1][1][0]+A[i]-B[i+K-1],dp[i-1][0][0]+A[i]-sum[i+K-1]+sum[i-1]);
			dp[i][1][1]=max(dp[i-1][1][1]+A[i]-B[i+K-1],dp[i-1][0][1]+A[i]-sum[i+K-1]+sum[i-1]);
		}
		else{
			dp[i][1][0]=max(dp[i-1][1][0]+A[i]-B[i+K-1-N],dp[i-1][0][0]+A[i]-sum[i+K-1-N]-sum[N-1]+sum[i-1]);
			dp[i][1][1]=max(dp[i-1][1][1]+A[i],dp[i-1][0][1]+A[i]-sum[N-1]+sum[i-1]);
		}
		//cout<<dp[i][1][1]<<endl;
	}
	//cout<<dp[n-1][1][1]<<endl;
	return max(max(dp[N-1][0][1],dp[N-1][1][0]),max(dp[N-1][1][1],dp[N-1][0][0]));
}
//signed main(){
//	cout<<solve(3,2,[40, 80, 100],[140, 0, 20]);
//}

Subtask #1
13.0 / 13.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 23800 KB Output is correct
2 Correct 5 ms 888 KB Output is correct
3 Correct 210 ms 96220 KB Output is correct
4 Correct 4 ms 1528 KB Output is correct
5 Correct 11 ms 2424 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 632 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 632 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 52 ms 23800 KB Output is correct
12 Correct 5 ms 888 KB Output is correct
13 Correct 210 ms 96220 KB Output is correct
14 Correct 4 ms 1528 KB Output is correct
15 Correct 11 ms 2424 KB Output is correct
16 Correct 201 ms 95408 KB Output is correct
17 Correct 85 ms 16120 KB Output is correct
18 Correct 146 ms 11840 KB Output is correct
19 Correct 144 ms 52144 KB Output is correct
20 Correct 156 ms 98376 KB Output is correct
21 Correct 140 ms 52304 KB Output is correct