oj.uz

Submission #844575

# Submission time Handle Problem Language Result Execution time Memory
844575 2023-09-05T14:14:52 Z vjudge1 Holding (COCI20_holding) C++17
88 / 110
 740 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"
#define all(aa) aa.begin(), aa.end()

int main(){
	int n, L, R, C;
	cin>>n>>L>>R>>C;

	vector<int> val(n+1);
	int ans=0;
	for(int i=1; i<=n; i++){
		cin>>val[i];
		if(i>=L && i<=R) ans+=val[i];
	}

	vector<vector<vector<int>>> dp_l(L+2, vector<vector<int>>(n+2, vector<int>(C+1)));
	for(int i=R; i>=L; i--){
		vector<vector<vector<int>>> dp(L+2, vector<vector<int>>(n+2, vector<int>(C+1)));
		for(int l=0; l<=L-1; l++){
			for(int r=n+1; r>=R+1; r--){
				for(int c=0; c<=C; c++){
					dp[l][r][c]=dp_l[l][r][c];
					if(l>0){
						if(c>=i-l)
							dp[l][r][c]=min(dp[l][r][c], dp_l[l-1][r][c-(i-l)]+val[l]-val[i]);
						dp[l][r][c]=min(dp[l][r][c], dp[l-1][r][c]);
					}
					if(r<=n){
						if(c>=r-i)
							dp[l][r][c]=min(dp[l][r][c], dp_l[l][r+1][c-(r-i)]+val[r]-val[i]);
						dp[l][r][c]=min(dp[l][r][c], dp[l][r+1][c]);
					}
				}
			}
		}
		dp_l=dp;
	}

	cout<<ans+dp_l[L-1][R+1][C];
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 548 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 11 ms 9708 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 548 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 11 ms 9708 KB Output is correct
8 Correct 3 ms 1348 KB Output is correct
9 Correct 5 ms 1804 KB Output is correct
10 Correct 5 ms 1560 KB Output is correct
11 Correct 13 ms 2548 KB Output is correct
12 Correct 4 ms 952 KB Output is correct
13 Correct 734 ms 112812 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 548 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 11 ms 9708 KB Output is correct
8 Correct 3 ms 1348 KB Output is correct
9 Correct 5 ms 1804 KB Output is correct
10 Correct 5 ms 1560 KB Output is correct
11 Correct 13 ms 2548 KB Output is correct
12 Correct 4 ms 952 KB Output is correct
13 Correct 734 ms 112812 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 3 ms 1972 KB Output is correct
16 Correct 2 ms 856 KB Output is correct
17 Correct 6 ms 2312 KB Output is correct
18 Correct 13 ms 3488 KB Output is correct
19 Correct 740 ms 112768 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 548 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 11 ms 9708 KB Output is correct
8 Correct 3 ms 1348 KB Output is correct
9 Correct 5 ms 1804 KB Output is correct
10 Correct 5 ms 1560 KB Output is correct
11 Correct 13 ms 2548 KB Output is correct
12 Correct 4 ms 952 KB Output is correct
13 Correct 734 ms 112812 KB Output is correct
14 Correct 1 ms 600 KB Output is correct
15 Correct 3 ms 1972 KB Output is correct
16 Correct 2 ms 856 KB Output is correct
17 Correct 6 ms 2312 KB Output is correct
18 Correct 13 ms 3488 KB Output is correct
19 Correct 740 ms 112768 KB Output is correct
20 Correct 113 ms 27152 KB Output is correct
21 Correct 68 ms 29068 KB Output is correct
22 Correct 2 ms 836 KB Output is correct
23 Runtime error 101 ms 262144 KB Execution killed with signal 9
24 Halted 0 ms 0 KB -