oj.uz

Submission #844652

# Submission time Handle Problem Language Result Execution time Memory
844652 2023-09-05T15:49:53 Z serifefedartar Holding (COCI20_holding) C++17
22 / 110
 68 ms 8772 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 20;
const ll MAXN = 1e6 + 5;

vector<int> A;
vector<vector<int>> dp;
int main() {
	fast
	int N, L, R, K;
	cin >> N >> L >> R >> K;

	A = vector<int>(N+1);
	dp = vector<vector<int>>(102, vector<int>(10205, 1e9));
	for (int i = 1; i <= N; i++)
		cin >> A[i];

	dp[0][0] = 0;
	int ans = 1e9;
	for (int i = 1; i <= N; i++) {
		vector<vector<int>> new_dp(102, vector<int>(10205, 1e9));
		for (int cnt = 0; cnt <= i; cnt++) {
			int cost = abs(L + cnt - i);
			for (int last = 0; last < K; last++) {
				new_dp[cnt][last] = min(new_dp[cnt][last], dp[cnt][last]); 
				new_dp[cnt + 1][cost + last] = min(new_dp[cnt + 1][cost + last], dp[cnt][last] + A[i]);
				if (cnt+1 == R - L + 1 && cost + last <= K)
					ans = min(ans, new_dp[cnt+1][cost+last]);
			}
		}
		dp = new_dp;
	}
	cout << ans << "\n"; 
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8632 KB Output is correct
2 Correct 18 ms 8684 KB Output is correct
3 Correct 19 ms 8700 KB Output is correct
4 Correct 18 ms 8684 KB Output is correct
5 Correct 20 ms 8684 KB Output is correct
6 Correct 20 ms 8684 KB Output is correct
7 Correct 18 ms 8684 KB Output is correct

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8632 KB Output is correct
2 Correct 18 ms 8684 KB Output is correct
3 Correct 19 ms 8700 KB Output is correct
4 Correct 18 ms 8684 KB Output is correct
5 Correct 20 ms 8684 KB Output is correct
6 Correct 20 ms 8684 KB Output is correct
7 Correct 18 ms 8684 KB Output is correct
8 Correct 68 ms 8772 KB Output is correct
9 Incorrect 65 ms 8736 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8632 KB Output is correct
2 Correct 18 ms 8684 KB Output is correct
3 Correct 19 ms 8700 KB Output is correct
4 Correct 18 ms 8684 KB Output is correct
5 Correct 20 ms 8684 KB Output is correct
6 Correct 20 ms 8684 KB Output is correct
7 Correct 18 ms 8684 KB Output is correct
8 Correct 68 ms 8772 KB Output is correct
9 Incorrect 65 ms 8736 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8632 KB Output is correct
2 Correct 18 ms 8684 KB Output is correct
3 Correct 19 ms 8700 KB Output is correct
4 Correct 18 ms 8684 KB Output is correct
5 Correct 20 ms 8684 KB Output is correct
6 Correct 20 ms 8684 KB Output is correct
7 Correct 18 ms 8684 KB Output is correct
8 Correct 68 ms 8772 KB Output is correct
9 Incorrect 65 ms 8736 KB Output isn't correct
10 Halted 0 ms 0 KB -