oj.uz

Submission #1017344

# Submission time Handle Problem Language Result Execution time Memory
1017344 2024-07-09T07:30:42 Z vjudge1 Holding (COCI20_holding) C++17
110 / 110
 41 ms 4444 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
int const N=105;
int const K=10005;
int const mod=1e9+7;

int dp_pre[2][N][K],dp_suf[N][2][K];
int arr[N];

int main(){
	int n,L,R,k;
	cin>>n>>L>>R>>k;
	for (int i = 1; i <=n; ++i)
		cin>>arr[i];
	int debt=0;
	for (int i = L; i <=R; ++i)
		debt+=arr[i];
	//compute dp_pre;
	for(int l=L-1;l>=1;l--)
		for(int r=L;r<=R;r++)
			for(int c=0;c<=k;c++){
				dp_pre[l%2][r][c]=max(dp_pre[(l+1)%2][r][c],dp_pre[l%2][r-1][c]);
				if(c>=r-l)
					dp_pre[l%2][r][c]=max(dp_pre[l%2][r][c],dp_pre[(l+1)%2][r-1][c-(r-l)]+max(0,(arr[r]-arr[l])));
			}
	//compute suf_dp;
	for(int r=R+1;r<=n;r++)
		for(int l=R;l>=L;l--)
			for(int c=0;c<=k;c++){
				dp_suf[l][r%2][c]=max(dp_suf[l+1][r%2][c],dp_suf[l][(r-1)%2][c]);
				if(c>=r-l)
					dp_suf[l][r%2][c]=max(dp_suf[l][r%2][c],dp_suf[(l+1)][(r-1)%2][c-(r-l)]+max(0,(arr[l]-arr[r])));
			}
	int mx=0;
	for(int i=L-1;i<=R;i++)
		for(int c=0;c<=k;c++)
			mx=max(dp_pre[1][i][c]+dp_suf[i+1][n%2][k-c],mx);
	cout<<debt-mx<<endl;
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2488 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 860 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2488 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 10 ms 2396 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2488 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 10 ms 2396 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 444 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 10 ms 2476 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2488 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 10 ms 2396 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 444 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 10 ms 2476 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 604 KB Output is correct
23 Correct 1 ms 576 KB Output is correct
24 Correct 2 ms 3420 KB Output is correct
25 Correct 41 ms 4444 KB Output is correct