oj.uz

Submission #334037

# Submission time Handle Problem Language Result Execution time Memory
334037 2020-12-08T07:20:05 Z ronnith Holding (COCI20_holding) C++14
110 / 110
 318 ms 20812 KB 
#include <bits/stdc++.h>

typedef long long ll;
#define v vector
#define vl vector<ll>
#define mk make_pair
#define f first
#define s second

using namespace std;

int main(){
	ll n, l, r, K;
	scanf("%lld%lld%lld%lld", &n, &l, &r, &K);
	ll a[n];
	for(int i = 0;i < n;i ++){
		scanf("%lld", &a[i]);
	}
	// int ans = INT_MAX;
	// for(int bit = 0;bit < (1<<n);bit ++){
	// 	if(__builtin_popcount(bit) == n - l + 1){
	// 		int sm = 0;
	// 		int cost = 0;
	// 		int h = l;
	// 		for(int i = 0;i < n;i ++){
	// 			if(!((1<<i)&bit))continue;
	// 			cost += h - (i + 1);
	// 			h ++;
	// 			sm += a[i];
	// 		}
	// 		if(cost <= k){
	// 			ans = min(ans, sm);
	// 		}
	// 	}
	// }
	// printf("%d\n", ans);
	ll ans = INT_MAX;
	v<v<vl>> dp1(2, v<vl>(r - l + 2, vl(K + 1, INT_MAX)));
	v<v<vl>> dp2(2, v<vl>(r - l + 2, vl(K + 1, INT_MAX)));
	int crr = 0;
	int prev = 1;
	for(int i = 0;i < n;i ++){
		for(int j = 0;j < r - l + 2;j ++){
			for(int k = 0;k <= K;k ++){
				dp1[crr][j][k] = dp2[crr][j][k] = INT_MAX;
				if(j == 0){
					dp2[crr][j][k] = 0;
				} else if(i == 0){
					if(j == 1){
						if(abs(l - i - 1) == k)
							dp1[crr][j][k] = a[i];
					} else {
						dp1[crr][j][k] = INT_MAX;
					}
				} else {
					if(abs(j - 1 + l - i - 1) <= k){
						dp1[crr][j][k] = a[i] + min(dp1[prev][j - 1][k - abs(j - 1 + l - i - 1)], dp2[prev][j - 1][k - abs(j - 1 + l - i - 1)]);// abs(j - 1 + l - i)
					}
					dp2[crr][j][k] = min(dp1[prev][j][k], dp2[prev][j][k]);
				}
				if(i == n - 1 and j == r - l + 1)
					ans = min(ans, min(dp1[crr][j][k], dp2[crr][j][k]));
			}
		}
		crr = 1 - crr;
		prev = 1 - prev;
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

holding.cpp: In function 'int main()':
holding.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |  scanf("%lld%lld%lld%lld", &n, &l, &r, &K);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
holding.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |   scanf("%lld", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 7 ms 3564 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 2 ms 492 KB Output is correct
13 Correct 87 ms 10988 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 7 ms 3564 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 2 ms 492 KB Output is correct
13 Correct 87 ms 10988 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 102 ms 10988 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 7 ms 3564 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 4 ms 492 KB Output is correct
12 Correct 2 ms 492 KB Output is correct
13 Correct 87 ms 10988 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 2 ms 492 KB Output is correct
19 Correct 102 ms 10988 KB Output is correct
20 Correct 4 ms 512 KB Output is correct
21 Correct 3 ms 492 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 6 ms 768 KB Output is correct
24 Correct 12 ms 1144 KB Output is correct
25 Correct 318 ms 20812 KB Output is correct