oj.uz

Submission #321327

# Submission time Handle Problem Language Result Execution time Memory
321327 2020-11-12T06:03:18 Z shivensinha4 Simfonija (COCI19_simfonija) C++17
110 / 110
 365 ms 3436 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 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

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.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 30 ms 3308 KB Output is correct
2 Correct 35 ms 3300 KB Output is correct
3 Correct 26 ms 3308 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3308 KB Output is correct
2 Correct 29 ms 3308 KB Output is correct
3 Correct 26 ms 3308 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3308 KB Output is correct
2 Correct 28 ms 3308 KB Output is correct
3 Correct 28 ms 3308 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 2744 KB Output is correct
2 Correct 214 ms 3404 KB Output is correct
3 Correct 251 ms 3300 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 3436 KB Output is correct
2 Correct 365 ms 3428 KB Output is correct
3 Correct 326 ms 3428 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 3428 KB Output is correct
2 Correct 170 ms 3396 KB Output is correct
3 Correct 339 ms 3396 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 3424 KB Output is correct
2 Correct 241 ms 3300 KB Output is correct
3 Correct 241 ms 3428 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 260 ms 3428 KB Output is correct
2 Correct 270 ms 3428 KB Output is correct
3 Correct 36 ms 3308 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 3308 KB Output is correct
2 Correct 26 ms 3308 KB Output is correct
3 Correct 174 ms 3392 KB Output is correct