oj.uz

Submission #462474

# Submission time Handle Problem Language Result Execution time Memory
462474 2021-08-10T15:54:47 Z Jasiekstrz Holding (COCI20_holding) C++17
110 / 110
 106 ms 14032 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e2;
const int K=1e4;
int tab[N+10];
int dp[2][N+10][K+10];
int bck[2][N+10][K+10];
void solve(int n,int x,int k,int t) // x - first inside 
{
	for(int j=1;j<=n;j++)
	{
		for(int c=0;c<=k;c++)
			dp[0][j][c]=dp[1][j][c]=0;
	}

	for(int i=x-1;i>=1;i--)
	{
		for(int j=1;j<=n;j++)
		{
			for(int c=0;c<=k;c++)
				dp[i%2][j][c]=0;
		}
		for(int j=x;j<=n;j++)
		{
			for(int c=0;c<=k;c++)
				dp[i%2][j][c]=min(dp[(i+1)%2][j][c],dp[i%2][j-1][c]);
			for(int c=j-i;c<=k;c++)
				dp[i%2][j][c]=min(dp[i%2][j][c],
						dp[(i+1)%2][j-1][c-j+i]+tab[i]-tab[j]);
		}
	}

	for(int i=x;i<=n;i++)
	{
		for(int c=0;c<=k;c++)
		{
			bck[t][i-x+1][c]=dp[1][i][c];
			//cerr<<"type="<<t<<" d="<<i-x+1<<" c="<<c<<" : "<<bck[t][i-x+1][c]<<"\n";
		}
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,l,r,k;
	cin>>n>>l>>r>>k;
	for(int i=1;i<=n;i++)
		cin>>tab[i];

	solve(n,l,k,0);
	reverse(tab+1,tab+n+1);
	solve(n,n-r+1,k,1);
	reverse(tab+1,tab+n+1);

	int ans=0;
	for(int i=0;i<=r-l+1;i++)
	{
		for(int c=0;c<=k;c++)
		{
			ans=min(ans,bck[0][i][c]+bck[1][r-l+1-i][k-c]);
			//cerr<<i<<" "<<c<<" "<<ans<<"\n";
		}
	}
	for(int i=l;i<=r;i++)
		ans+=tab[i];
	cout<<ans<<"\n";
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 1996 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 1996 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Correct 2 ms 972 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1092 KB Output is correct
13 Correct 21 ms 7200 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 1996 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Correct 2 ms 972 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1092 KB Output is correct
13 Correct 21 ms 7200 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 1 ms 960 KB Output is correct
16 Correct 1 ms 956 KB Output is correct
17 Correct 1 ms 972 KB Output is correct
18 Correct 2 ms 1100 KB Output is correct
19 Correct 21 ms 7200 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 2 ms 1996 KB Output is correct
8 Correct 1 ms 972 KB Output is correct
9 Correct 1 ms 972 KB Output is correct
10 Correct 2 ms 972 KB Output is correct
11 Correct 1 ms 1100 KB Output is correct
12 Correct 1 ms 1092 KB Output is correct
13 Correct 21 ms 7200 KB Output is correct
14 Correct 1 ms 844 KB Output is correct
15 Correct 1 ms 960 KB Output is correct
16 Correct 1 ms 956 KB Output is correct
17 Correct 1 ms 972 KB Output is correct
18 Correct 2 ms 1100 KB Output is correct
19 Correct 21 ms 7200 KB Output is correct
20 Correct 4 ms 1996 KB Output is correct
21 Correct 10 ms 2244 KB Output is correct
22 Correct 1 ms 1612 KB Output is correct
23 Correct 15 ms 5848 KB Output is correct
24 Correct 3 ms 2244 KB Output is correct
25 Correct 106 ms 14032 KB Output is correct