oj.uz

Submission #96349

# Submission time Handle Problem Language Result Execution time Memory
96349 2019-02-08T15:15:32 Z KLPP Homecoming (BOI18_homecoming) C++14
31 / 100
 1000 ms 43412 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define INF 10000000000000000
lld DP[1000000][2];
int n,k;
lld C[1000000];
lld D[1000000];
lld compute(int pos, int type){
	if(DP[pos][type]!=-1)return DP[pos][type];
	if(type==0){
		DP[pos][type]=max(compute(pos-1,0),compute(pos-1,1)+D[pos-1]);
	}
	if(type==1){
		DP[pos][type]=max(compute(pos-1,0),compute(pos-1,1)+C[pos-1]);
	}
	
	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[0][0]=0;
	DP[0][1]=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<2;j++)cout<<compute(i,j)<<" ";
		cout<<endl;
	}*/
	return compute(n,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 7 ms 376 KB Output is correct
5 Correct 3 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 7 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 508 ms 888 KB Output is correct
7 Correct 503 ms 828 KB Output is correct
8 Correct 134 ms 632 KB Output is correct
9 Correct 509 ms 868 KB Output is correct
10 Correct 3 ms 380 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 43412 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 7 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 508 ms 888 KB Output is correct
7 Correct 503 ms 828 KB Output is correct
8 Correct 134 ms 632 KB Output is correct
9 Correct 509 ms 868 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Execution timed out 1076 ms 43412 KB Time limit exceeded
12 Halted 0 ms 0 KB -