Submission #321327

#	Time	Username	Problem	Language	Result	Execution time	Memory
321327		shivensinha4	Simfonija (COCI19_simfonija)	C++17	110 / 110	365 ms	3436 KiB

simfonija

#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 n, k;
vector<ll> nums, pref;

ll f(ll mid, ll st, ll end) {
	ll nn = end-st+1;
	if (mid >= 0) {
		int excl = lower_bound(nums.begin()+st, nums.begin()+end+1, -mid) - nums.begin();
		int excr = upper_bound(nums.begin()+st, nums.begin()+end+1, 0) - nums.begin();
		ll rem = mid * (2*excl-st-end-1);
		// cout << excl << " " << excr << "..." << rem << endl;
		if (excl < excr) rem += 2 * (pref[excr-1] - (excl > 0 ? pref[excl-1] : 0));
		// cout << mid << " -> " << rem << endl;
		return rem;
	}
	
	int excr = upper_bound(nums.begin()+st, nums.begin()+end+1, -mid) - nums.begin();
	int excl = (lower_bound(nums.begin()+st, nums.begin()+end+1, 0) - nums.begin());
	ll rem = (end+st+1-2*excr) * abs(mid);
	// cout << ".." << excl << " " << excr << " " << rem << endl;
	if (excl < excr) rem += 2 * (pref[excr-1] - (excl > 0 ? pref[excl-1] : 0));
	// cout << mid << " -> " << rem << " " << 2 * (pref[excr-1] - (excl > 0 ? pref[excl-1] : 0)) << endl;
	return rem;
}

int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> k;
	nums.resize(n); pref.resize(n);
	for_(i, 0, n) cin >> nums[i];
	for_(i, 0, n) {
		ll v; cin >> v;
		nums[i] -= v;
	}
	
	// for (int i: nums) cout << i << " ";
	// cout << endl;
	
	sort(nums.begin(), nums.end());
	for_(i, 0, n) {
		pref[i] = abs(nums[i]);
		if (i > 0) pref[i] += pref[i-1];
	}
	 
	ll ans = n == k ? 0 : LONG_LONG_MAX;
	if (n > k) for_(st, 0, n) {
		int end = n-k-1+st;
		if (st > end or st > k) {
			break;
		}
		
		
		// cout << "array from " << st << " " << end << " " << " with sum " << pref[end] - (st > 0 ? pref[st-1] : 0) << endl;
		
		ll l = -nums[end], r = -nums[st];
		while (r-l >= 3) {
			ll m1 = l + (r-l) / 3, m2 = r - (r-l) / 3;
			if (f(m1, st, end) < f(m2, st, end)) l = m1;
			else r = m2;
		}
		
		ll rem = 0;
		for_(i, l, r+1) rem = max(rem, f(i, st, end));
		ans = min(ans, pref[end] - (st > 0 ? pref[st-1] : 0) - rem);
	}
	
	cout << ans << endl;

	return 0;
}

Compilation message (stderr)

simfonija.cpp: In function 'll f(ll, ll, ll)':
simfonija.cpp:14:5: warning: unused variable 'nn' [-Wunused-variable]
   14 |  ll nn = end-st+1;
      |     ^~

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 11 / 11
• Subtask 5: 11 / 11
• Subtask 6: 11 / 11
• Subtask 7: 11 / 11
• Subtask 8: 11 / 11
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11