Submission #844743

#	Time	Username	Problem	Language	Result	Execution time	Memory
844743		vjudge1	Holding (COCI20_holding)	C++17	22 / 110	2 ms	1628 KiB

holding

#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 (stderr)

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 / 22
• Subtask 2: 0 / 33
• Subtask 3: 0 / 33
• Subtask 4: 0 / 22