oj.uz

Submission #96345

# Submission time Handle Problem Language Result Execution time Memory
96345 2019-02-08T14:50:33 Z KLPP Homecoming (BOI18_homecoming) C++14
31 / 100
 1000 ms 56780 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define INF 10000000000000000
lld DP[1000000][3];
int n,k;
lld C[1000000];
lld D[1000000];
lld compute(int pos, int type){
	if(type==2 && pos+k>n)return -INF;
	if(DP[pos][type]!=-1)return DP[pos][type];
	if(type==0){
		DP[pos][type]=max(compute(pos-1,0),compute(pos-1,2));
	}
	if(type==1){
		DP[pos][type]=max(compute(pos-1,0),compute(pos-1,1))+C[pos];
	}
	if(type==2){
		DP[pos][type]=max(compute(pos-1,0),compute(pos-1,1))+D[pos];
	}DP[pos][type]=max(DP[pos][type],(lld)0);
	return DP[pos][type];
}
lld solveLin(int A[], int B[]){
	
	for(int i=0;i<n;i++){
		C[i]=A[i]-B[i];
	}
	D[0]=A[0];
	for(int i=0;i<k;i++)D[0]-=B[i];
	for(int i=0;i+k<n;i++){
		D[i+1]=D[i]-A[i]+B[i]+A[i+1]-B[i+k];
	}
	for(int i=n-k+1;i<n;i++){
		D[i]=-INF;
	}
	for(int i=0;i<n;i++){
		DP[i][0]=-1;
		DP[i][1]=-1;
		DP[i][2]=-1;
	}
	DP[0][0]=0;
	DP[0][1]=C[0];
	DP[0][2]=D[0];
	/*cout<<compute(n-1,0)<<" "<<compute(n-1,1)<<" "<<compute(n-1,2)<<endl;
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++)cout<<DP[i][j]<<" ";
		cout<<endl;
	}*/
	return compute(n-1,0);
}
long long solve(int N, int K, int *A, int *B){
	n=N;
	k=K;
	lld sol=0;
	for(int i=0;i<n;i++)sol+=A[i]-B[i];
	sol=max(sol,(lld)0);
	for(int i=0;i<n;i++){
		sol=max(sol,solveLin(A,B));
		for(int j=0;j<n-1;j++){
			swap(A[j],A[j+1]);
			swap(B[j],B[j+1]);
		}//for(int j=0;j<n;j++)cout<<A[j]<<" "<<B[j]<<endl;
	}	
	return sol;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 10 ms 376 KB Output is correct
5 Correct 4 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 6 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 10 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 346 ms 1016 KB Output is correct
7 Correct 450 ms 964 KB Output is correct
8 Correct 163 ms 732 KB Output is correct
9 Correct 698 ms 940 KB Output is correct
10 Correct 3 ms 504 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 56780 KB Time limit exceeded
2 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 6 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 10 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 346 ms 1016 KB Output is correct
7 Correct 450 ms 964 KB Output is correct
8 Correct 163 ms 732 KB Output is correct
9 Correct 698 ms 940 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Execution timed out 1084 ms 56780 KB Time limit exceeded
12 Halted 0 ms 0 KB -