oj.uz

Submission #456225

# Submission time Handle Problem Language Result Execution time Memory
456225 2021-08-06T09:15:57 Z grt Holding (COCI20_holding) C++17
110 / 110
 127 ms 98516 KB 
#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 110, kax = 10000 + 10;
int n, l, r, k;
int val[nax];
int dp[nax][nax][kax];
int dp2[nax][nax][kax];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> l >> r >> k;
	for(int i = 1; i <= n; ++i) {
		cin >> val[i];
	}
	for(int p1 = 1; p1 < l; p1++) {
		for(int p2 = l; p2 <= r; p2++) {
			for(int f = 0; f <= k; ++f) {
				dp[p1][p2][f] = min({dp[p1 - 1][p2][f], dp[p1][p2 - 1][f]});
				if(p2 - p1 <= f) {
					dp[p1][p2][f] = min(dp[p1][p2][f], dp[p1 - 1][p2 - 1][f - (p2 - p1)]  + val[p1] - val[p2]);
				}
			}
		}
	}
	for(int p1 = r + 1; p1 <= n; p1++) {
		for(int p2 = r; p2 >= l; p2--) {
			for(int f = 0; f <= k; ++f) {
				dp2[p1][p2][f] = min({dp2[p1 - 1][p2][f], dp2[p1][p2 + 1][f]});
				if(p1 - p2 <= f) {
					dp2[p1][p2][f] = min(dp2[p1][p2][f], dp2[p1 - 1][p2 + 1][f - (p1 - p2)] + val[p1] - val[p2]);
				}
			}
		}
	}
	int ans = 0;
	ans = min(ans, dp2[n][l][k]);
	for(int p = l; p <= r; ++p) {
		for(int k1 = 0; k1 <= k; ++k1) {
			ans = min(ans, dp[l - 1][p][k1] + dp2[n][p + 1][k - k1]);
		}
	}
	for(int i = l; i <= r; ++i) ans += val[i];
	cout << ans;
}

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 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 1612 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 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 1612 KB Output is correct
8 Correct 2 ms 2508 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 3148 KB Output is correct
11 Correct 2 ms 3276 KB Output is correct
12 Correct 1 ms 1996 KB Output is correct
13 Correct 29 ms 24868 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 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 1612 KB Output is correct
8 Correct 2 ms 2508 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 3148 KB Output is correct
11 Correct 2 ms 3276 KB Output is correct
12 Correct 1 ms 1996 KB Output is correct
13 Correct 29 ms 24868 KB Output is correct
14 Correct 1 ms 704 KB Output is correct
15 Correct 1 ms 1228 KB Output is correct
16 Correct 1 ms 1740 KB Output is correct
17 Correct 1 ms 1868 KB Output is correct
18 Correct 2 ms 2892 KB Output is correct
19 Correct 28 ms 24856 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 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 2 ms 1612 KB Output is correct
8 Correct 2 ms 2508 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 3148 KB Output is correct
11 Correct 2 ms 3276 KB Output is correct
12 Correct 1 ms 1996 KB Output is correct
13 Correct 29 ms 24868 KB Output is correct
14 Correct 1 ms 704 KB Output is correct
15 Correct 1 ms 1228 KB Output is correct
16 Correct 1 ms 1740 KB Output is correct
17 Correct 1 ms 1868 KB Output is correct
18 Correct 2 ms 2892 KB Output is correct
19 Correct 28 ms 24856 KB Output is correct
20 Correct 5 ms 6604 KB Output is correct
21 Correct 3 ms 3180 KB Output is correct
22 Correct 3 ms 4812 KB Output is correct
23 Correct 5 ms 4300 KB Output is correct
24 Correct 8 ms 12236 KB Output is correct
25 Correct 127 ms 98516 KB Output is correct