oj.uz

Submission #291101

# Submission time Handle Problem Language Result Execution time Memory
291101 2020-09-04T16:42:21 Z penguinhacker Holding (COCI20_holding) C++17
110 / 110
 161 ms 2936 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int INF=1e9;
int n, l, r, k, a[100];
//int dp[10000][100]; //minimum cost given used i operations and have selected from first j elements

//what do we need to know
//we need cost used, used first [] elements, and have chosen first [] elements
//maybe only maintain 2 things, such as cost, and chosen first [] elements

void debug(vector<vector<int>> &v) {
	for (auto& x: v) {
		for (int i: x) cout << i << " ";
		cout << "\n";
	}
	cout << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> l >> r >> k, --l, --r;
	for (int i=0; i<n; ++i) cin >> a[i];
	//memset(dp, 0x3f, sizeof(dp));
	vector<vector<int>> dp(k+1, vector<int>(r-l+2, INF));
	dp[0][0]=0;
	for (int pos=0; pos<n; ++pos) {
		//vector<vector<int>> dpl=dp;
		for (int i=min(r-l+1, pos+1); i>0; --i) {
			int cost=abs(l+i-1-pos);
			for (int j=k; j>=cost; --j) dp[j][i]=min(dp[j][i], dp[j-cost][i-1]+a[pos]);
			//for (int j=cost; j<=k; ++j) dp[j][i]=min(dp[j][i], dpl[j-cost][i-1]+a[pos]);
		}
		//debug(dp);
	}
	int ans=INF;
	for (int i=0; i<=k; ++i) ans=min(ans, dp[i][r-l+1]);
	cout << ans << "\n";
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 4 ms 1024 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 4 ms 1024 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 40 ms 1792 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 4 ms 1024 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 40 ms 1792 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 40 ms 1792 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 4 ms 1024 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 40 ms 1792 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 40 ms 1792 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 3 ms 512 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 161 ms 2936 KB Output is correct