oj.uz

Submission #321244

# Submission time Handle Problem Language Result Execution time Memory
321244 2020-11-11T16:44:59 Z shivensinha4 Simfonija (COCI19_simfonija) C++17
66 / 110
 45 ms 6752 KB 
#include "bits/stdc++.h"
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
// #define endl '\n'


int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, k; cin >> n >> k;
	vector<ll> nums(n);
	for_(i, 0, n) cin >> nums[i];
	ll init = 0;
	
	for_(i, 0, n) {
		int v; cin >> v;
		nums[i] -= v;
		init += abs(nums[i]);
	}
	
	sort(nums.begin(), nums.end());
	vector<ll> neg, pos, geq, leq, changeNeg, changePos, prefNeg, prefPos, origNeg, origPos, sufNeg, sufPos;
	for_(i, 0, n) {
		if (nums[i] == 0) continue;
		if (nums[i] < 0) {
			neg.push_back(-nums[i]);
			leq.push_back(i+1);
		} else {
			pos.push_back(nums[i]);
			geq.push_back(n-i);
		}
	}
	
	k = min(k, (int) pos.size() + (int) neg.size());
	
	reverse(neg.begin(), neg.end()); reverse(leq.begin(), leq.end());
	
	prefNeg = sufNeg = origNeg = neg; prefPos = sufPos = origPos = pos;
	for_(i, 1, prefNeg.size()) prefNeg[i] += prefNeg[i-1]-neg[i-1];
	for_(i, 1, prefPos.size()) prefPos[i] += prefPos[i-1]-pos[i-1];
	for (int i = neg.size()-2; i >= 0; i--) sufNeg[i] += sufNeg[i+1];
	for (int i = pos.size()-2; i >= 0; i--) sufPos[i] += sufPos[i+1];
	
	int negRem = min(k, (int) neg.size()), posRem = min(k-negRem, (int) pos.size());
	int lt = min((int) pos.size()-posRem, negRem)+1;
	
	for_(i, 0, neg.size()) leq[i] -= negRem;
	for_(i, 0, pos.size()) geq[i] -= posRem;
	
	for_(i, 0, neg.size()) {
		if (i > 0) origNeg[i] -= neg[i-1];
		origNeg[i] *= 2*leq[i]-n+k;
		if (i > 0) origNeg[i] += origNeg[i-1];
	}
	for_(i, 0, pos.size()) {
		if (i > 0) origPos[i] -= pos[i-1];
		origPos[i] *= 2*geq[i]-n+k;
		if (i > 0) origPos[i] += origPos[i-1];
	}
	
	ll ans = init;
	for_(iter, 0, lt) {
		ll curr = init - (posRem > 0 ? sufPos[pos.size()-posRem] : 0) - (negRem > 0 ? sufNeg[neg.size()-negRem] : 0);
		// cout << curr << " " << (posRem > 0 ? sufPos[pos.size()-posRem] : 0)  << " " << (negRem > 0 ? sufNeg[neg.size()-negRem] : 0) << endl;
		
		int negLeft = neg.size()-negRem, posLeft = pos.size()-posRem;
		if (negLeft > posLeft) {
			int l = 0, r = neg.size()-negRem, idx = -1;
			while (l < r) {
				int mid = (l+r)/2;
				if (2*leq[mid]-n+k+2*iter >= 0) {
					idx = mid; l = mid+1;
				} else r = mid;
			}
			
			if (idx != -1) curr -= origNeg[idx] + prefNeg[idx]*2*iter;
		} else if (posLeft > negLeft) {
			int l = 0, r = pos.size()-posRem, idx = -1;
			while (l < r) {
				int mid = (l+r)/2;
				if (2*geq[mid]-n+k-2*iter >= 0) {
					idx = mid; l = mid+1;
				} else r = mid;
			}
			
			if (idx != -1) curr -= origPos[idx] - prefPos[idx]*2*iter; // what really happened here?
		}
		
		
		// cout << " -> " << curr << endl;
		ans = min(ans, curr);
		negRem -= 1; posRem += 1;
	}
	
	cout << ans << endl;

	return 0;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5208 KB Output is correct
2 Correct 33 ms 5208 KB Output is correct
3 Correct 29 ms 5080 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5208 KB Output is correct
2 Correct 31 ms 5208 KB Output is correct
3 Correct 29 ms 5336 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 5208 KB Output is correct
2 Correct 31 ms 5208 KB Output is correct
3 Correct 29 ms 5204 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 5212 KB Output is correct
2 Incorrect 30 ms 6528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 5208 KB Output is correct
2 Incorrect 35 ms 6624 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5208 KB Output is correct
2 Correct 33 ms 6612 KB Output is correct
3 Correct 35 ms 6616 KB Output is correct

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 5208 KB Output is correct
2 Incorrect 35 ms 6648 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5204 KB Output is correct
2 Incorrect 40 ms 6616 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5208 KB Output is correct
2 Correct 32 ms 6752 KB Output is correct
3 Correct 36 ms 6616 KB Output is correct