oj.uz

Submission #844743

# Submission time Handle Problem Language Result Execution time Memory
844743 2023-09-05T19:29:02 Z vjudge1 Holding (COCI20_holding) C++17
22 / 110
 2 ms 1628 KB 
#include <bits/stdc++.h>
#define fast cin.tie(0)->sync_with_stdio(0);
#define int long long
#define inf ((int)1e18)
#define N 10001
using namespace std;
vector <vector<int> > state(N);
vector <int> svalue(N), arr;

int32_t main(){
	fast
	int n, l, r, k;
	cin>>n>>l>>r>>k;
	l--, r--;
	for(int i = 0; i < n; i++) {
		int in;
		cin>>in;
		arr.push_back(in);
	}
	int tval = 0;
	for(int i = l; i <= r; i++) {
		tval += arr[i];
	}
	state[0] = arr;
	svalue[0] = tval;

	for(int i = 1; i <= k; i++) {
		// cout<<"\nK: "<<i<<"\n\n";
		int minCost = inf, index;
		for(int j = max(0ll ,i - n - 1); j < i; j++) { // look to this cost state
			// cout<<"J: "<<j<<"\n";
			int cost = i - j;
			int best = 0; //max change on best swap
			for(int p = 0; p < n - cost; p++) {
				int val = 0;
				bool isInside1 = (p >= l and p <= r);
				bool isInside2 = (p + cost >= l and p + cost <= r);
				if(isInside1 == isInside2) continue;

				if(isInside1) {
					val -= state[j][p];
					val += state[j][p + cost];
				}
				else {
					val += state[j][p];
					val -= state[j][p + cost];
				}

				best = min(best, val);

			}
			int sumCost = svalue[j] + best;
			if(sumCost < minCost) {
				index = j;
				minCost = sumCost;
			}
			// cout<<sumCost<<" "<<minCost<<"\n";
		}
		// cout<<"index: "<<index<<"\n";
		
		state[i] = state[index];
		svalue[i] = minCost;

		

		int cost = i - index;
		int best = 0, bestIndex = -1; //max change on best swap
		for(int p = 0; p < n - cost; p++) {
			int val = 0;
			bool isInside1 = (p >= l and p <= r);
			bool isInside2 = (p + cost >= l and p + cost <= r);
			if(isInside1 == isInside2) continue;

			if(isInside1) {
				val -= state[index][p];
				val += state[index][p + cost];
			}
			else {
				val += state[index][p];
				val -= state[index][p + cost];
			}

			if(val < best) {
				best = val;
				bestIndex = p;
			}
		}
		// cout<<"swapping: "<<bestIndex<<" "<<bestIndex+cost<<"\n";
		// cout<<"result: "<<svalue[i]<<"\n";
		if(~bestIndex)
			swap(state[i][bestIndex], state[i][bestIndex + cost]);
		// for(auto it:state[i]) {
		// 	cout<<it<<" ";
		// }cout<<"\n";
	}
	//TODO: dont forget to clear vectors
	cout<<svalue[k];
}

Compilation message

holding.cpp: In function 'int32_t main()':
holding.cpp:66:7: warning: 'index' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |   int cost = i - index;
      |       ^~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Incorrect 1 ms 600 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Incorrect 1 ms 600 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 0 ms 600 KB Output is correct
7 Correct 2 ms 1628 KB Output is correct
8 Correct 1 ms 600 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 876 KB Output is correct
12 Incorrect 1 ms 600 KB Output isn't correct
13 Halted 0 ms 0 KB -