oj.uz

Submission #249679

# Submission time Handle Problem Language Result Execution time Memory
249679 2020-07-15T14:22:16 Z dvdg6566 Holding (COCI20_holding) C++14
55 / 110
 72 ms 4472 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end() 
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=105;
const ll MAXK=10100;
const ll INF = 1e9;
const ll MOD = 1e9+7;

int dpleft[MAXN][MAXK][2];
int dpright[MAXN][MAXK][2];
int rightends[MAXN][MAXK];
int leftends[MAXN][MAXK];
int N,L,R,K;
int A[MAXN];

int askLeft(int l,int r,int k){
	if(l<0||k<0)return INF;
	if(dpleft[l][k][1]!=-1)return dpleft[l][k][1];
	int ans=INF;
	ans=min(ans,askLeft(l-1,r,k));
	// choose to swap
	int len=(r-l);
	if(k>=len&&l>0)ans=min(ans,dpleft[l-1][k-len][0]+A[l]);
	// chose to not swap
	ans=min(ans,A[r]+dpleft[l][k][0]);
	return dpleft[l][k][1]=ans;
}

int askRight(int l,int r,int k){
	if(r>N+1||k<0)return INF;
	if(dpright[r][k][1]!=-1)return dpright[r][k][1];
	int ans=INF;
	ans=min(ans,askRight(l,r+1,k));
	// choose to swap
	int len=(r-l);
	if(k>=len&&r<N+1)ans=min(ans,dpright[r+1][k-len][0]+A[r]);
	// chose to not swap
	ans=min(ans,A[l]+dpright[r][k][0]);
	return dpright[r][k][1]=ans;
}

int main(){
	cin>>N>>L>>R>>K;
	for(int i=1;i<=N;++i)cin>>A[i];
	for(int l=0;l<L;++l)for(int k=0;k<=K;++k){
		dpleft[l][k][0]=INF;
		dpleft[l][k][1]=-1;
	}
	for(int i=0;i<L;++i)dpleft[i][0][0]=0;
	for(int r=L;r<=R;++r){
		for(int k=0;k<=K;++k){
			rightends[r][k]=askLeft(L-1,r,k);
		}

		for(int l=0;l<L;++l)for(int k=0;k<=K;++k){
			dpleft[l][k][0]=dpleft[l][k][1];
			dpleft[l][k][1]=-1;
		}
	}

	for(int r=R+1;r<=N+1;++r)for(int k=0;k<=K;++k){
		dpright[r][k][0]=INF;
		dpright[r][k][1]=-1;
	}
	for(int i=R+1;i<=N+1;++i)dpright[i][0][0]=0;
	for(int l=R;l>=L;--l){
		for(int k=0;k<=K;++k){
			leftends[l][k]=askRight(l,R+1,k);
		}
		for(int r=R+1;r<=N+1;++r)for(int k=0;k<=K;++k){
			dpright[r][k][0]=dpright[r][k][1];
			dpright[r][k][1]=-1;
		}
	}

	// for(int div=L;div<=R;++div){
	// 	cout<<"Stop left side at "<<div<<'\n';
	// 	for(int k=0;k<=K;++k)cout<<rightends[div][k]<<' ';cout<<'\n';
	// }

	// for(int div=L;div<=R;++div){
	// 	cout<<"Stop right side at "<<div<<'\n';
	// 	for(int k=0;k<=K;++k)cout<<leftends[div][k]<<' ';cout<<'\n';
	// }

	int res=INF;
	for(int div=L-1;div<=R;++div){
		for(int k=0;k<=K;++k){
			res=min(res, rightends[div][k] + leftends[div+1][K-k]);
		}	
	}
	cout<<res;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 512 KB Output is correct
7 Correct 5 ms 1408 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 512 KB Output is correct
7 Correct 5 ms 1408 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 1 ms 768 KB Output is correct
13 Correct 72 ms 4472 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 512 KB Output is correct
7 Correct 5 ms 1408 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 1 ms 768 KB Output is correct
13 Correct 72 ms 4472 KB Output is correct
14 Correct 0 ms 512 KB Output is correct
15 Correct 1 ms 640 KB Output is correct
16 Incorrect 1 ms 640 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 512 KB Output is correct
7 Correct 5 ms 1408 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 1 ms 768 KB Output is correct
13 Correct 72 ms 4472 KB Output is correct
14 Correct 0 ms 512 KB Output is correct
15 Correct 1 ms 640 KB Output is correct
16 Incorrect 1 ms 640 KB Output isn't correct
17 Halted 0 ms 0 KB -