oj.uz

Submission #848372

# Submission time Handle Problem Language Result Execution time Memory
848372 2023-09-12T09:46:52 Z Onur_Ilgaz Holding (COCI20_holding) C++17
110 / 110
 201 ms 16592 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 105
using namespace std;
int arr[N];

int32_t main(){
	fast
	int n, l, r, money;
	cin>>n>>l>>r>>money;
	int sum = 0;
	for(int i = 1; i <= n; i++) {
		cin>>arr[i];
		if(i >= l and i <= r) sum += arr[i];
	}
	vector <vector<int> > dp(n + 2, vector<int> (money + 1, inf));
	dp[l][0] = sum;
	for(int i = 1; i <= n; i++) { // from
		if(i >= l and i <= r) continue; //!
		vector <vector<int> > ndp = dp;

		for(int j = l; j <= r; j++) { // to
			for(int k = 0; k <= money; k++) { // k
				// swapped j and i
				if(k + abs(i - j) <= money) {
					// cout<<i<<" "<<j<<" | ";
					ndp[j + 1][k + abs(i - j)] = min(
						ndp[j + 1][k + abs(i - j)],
						dp[j][k] + (arr[i] - arr[j])
					);
					// if(ndp[j + 1][k + abs(i - j)] < 100) 
						// cout<<j + 1<<" "<<k + abs(i - j)<<" "<<ndp[j + 1][k + abs(i - j)]<<"\n";
				}
				dp[j + 1][k] = min(
					dp[j + 1][k], 
					dp[j][k]
				);
			}
		}
		dp = ndp;
		// cout<<"changed\n\n";
	}
	// cout<<"dp: ";
	for(auto &it:dp) {
		for(auto &itt:it) {
			sum = min(sum, itt);
			// if(itt < 100) cout<<itt<<" ";
		}
	}
	cout<<sum;
}

Subtask #1
22.0 / 22.0

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

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3 ms 2708 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 44 ms 8752 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3 ms 2708 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 44 ms 8752 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 44 ms 8792 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 3 ms 2708 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 1 ms 600 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 44 ms 8752 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 44 ms 8792 KB Output is correct
20 Correct 8 ms 1348 KB Output is correct
21 Correct 14 ms 1828 KB Output is correct
22 Correct 1 ms 344 KB Output is correct
23 Correct 87 ms 7036 KB Output is correct
24 Correct 4 ms 940 KB Output is correct
25 Correct 201 ms 16592 KB Output is correct