oj.uz

Submission #249654

# Submission time Handle Problem Language Result Execution time Memory
249654 2020-07-15T13:57:01 Z dvdg6566 Holding (COCI20_holding) C++14
0 / 110
 4 ms 8192 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=100;
const ll MAXK=10100;
const ll INF = 1e9;
const ll MOD = 1e9+7;

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

int ask(int l,int r,int k){
	if(dpleft[l][k][1]!=-1)return dpleft[l][k][1];
	if(l<0||k<0)return dpleft[l][k][1]=INF;
	int ans=INF;
	if(l+1<L)ans=min(ans,ask(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 main(){
	memset(dpleft,-1,sizeof(dpleft));
	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;
	}
	assert(R==N);
	for(int i=0;i<L;++i)dpleft[i][0][0]=0;
	for(int r=L;r<=R;++r){
		for(int l=0;l<L;++l)for(int k=0;k<=K;++k)ask(l,r,k);
		// cout<<"When right pointer at "<<r<<'\n';
		// for(int l=0;l<L;++l){
		// 	cout<<"Left at "<<l<<'\n';
		// 	for(int k=0;k<=K;++k)cout<<ask(l,r,k)<<' ';cout<<'\n';
		// }
		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;
		}
	}
	int res=INF;
	for(int k=0;k<=K;++k){
		res=min(res,dpleft[0][k][0]);
	}
	cout<<res;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8192 KB Output is correct
2 Correct 4 ms 8192 KB Output is correct
3 Correct 4 ms 8192 KB Output is correct
4 Incorrect 4 ms 8192 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8192 KB Output is correct
2 Correct 4 ms 8192 KB Output is correct
3 Correct 4 ms 8192 KB Output is correct
4 Incorrect 4 ms 8192 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8192 KB Output is correct
2 Correct 4 ms 8192 KB Output is correct
3 Correct 4 ms 8192 KB Output is correct
4 Incorrect 4 ms 8192 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8192 KB Output is correct
2 Correct 4 ms 8192 KB Output is correct
3 Correct 4 ms 8192 KB Output is correct
4 Incorrect 4 ms 8192 KB Output isn't correct
5 Halted 0 ms 0 KB -