oj.uz

Submission #249657

# Submission time Handle Problem Language Result Execution time Memory
249657 2020-07-15T14:01:00 Z dvdg6566 Holding (COCI20_holding) C++14
55 / 110
 75 ms 16512 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(l<0||k<0)return INF;
	if(dpleft[l][k][1]!=-1)return dpleft[l][k][1];
	int ans=INF;
	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[L-1][k][0]);
	}
	cout<<res;
}

Subtask #1
22.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 5 ms 8192 KB Output is correct
4 Correct 4 ms 8192 KB Output is correct
5 Correct 5 ms 8192 KB Output is correct
6 Correct 4 ms 8192 KB Output is correct
7 Correct 9 ms 8192 KB Output is correct

Subtask #2
33.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 5 ms 8192 KB Output is correct
4 Correct 4 ms 8192 KB Output is correct
5 Correct 5 ms 8192 KB Output is correct
6 Correct 4 ms 8192 KB Output is correct
7 Correct 9 ms 8192 KB Output is correct
8 Correct 5 ms 8192 KB Output is correct
9 Correct 5 ms 8192 KB Output is correct
10 Correct 6 ms 8192 KB Output is correct
11 Correct 6 ms 8192 KB Output is correct
12 Correct 5 ms 8192 KB Output is correct
13 Correct 75 ms 8192 KB Output is correct

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 5 ms 8192 KB Output is correct
4 Correct 4 ms 8192 KB Output is correct
5 Correct 5 ms 8192 KB Output is correct
6 Correct 4 ms 8192 KB Output is correct
7 Correct 9 ms 8192 KB Output is correct
8 Correct 5 ms 8192 KB Output is correct
9 Correct 5 ms 8192 KB Output is correct
10 Correct 6 ms 8192 KB Output is correct
11 Correct 6 ms 8192 KB Output is correct
12 Correct 5 ms 8192 KB Output is correct
13 Correct 75 ms 8192 KB Output is correct
14 Runtime error 14 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 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 5 ms 8192 KB Output is correct
4 Correct 4 ms 8192 KB Output is correct
5 Correct 5 ms 8192 KB Output is correct
6 Correct 4 ms 8192 KB Output is correct
7 Correct 9 ms 8192 KB Output is correct
8 Correct 5 ms 8192 KB Output is correct
9 Correct 5 ms 8192 KB Output is correct
10 Correct 6 ms 8192 KB Output is correct
11 Correct 6 ms 8192 KB Output is correct
12 Correct 5 ms 8192 KB Output is correct
13 Correct 75 ms 8192 KB Output is correct
14 Runtime error 14 ms 16512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -