oj.uz

Submission #321333

# Submission time Handle Problem Language Result Execution time Memory
321333 2020-11-12T06:14:58 Z shivensinha4 Simfonija (COCI19_simfonija) C++17
110 / 110
 367 ms 2032 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);
		if (excl < excr) rem += 2 * (pref[excr-1] - (excl > 0 ? pref[excl-1] : 0));
		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);
	if (excl < excr) rem += 2 * (pref[excr-1] - (excl > 0 ? pref[excl-1] : 0));
	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;
	}
	
	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;
		}
		
		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 1968 KB Output is correct
2 Correct 27 ms 1900 KB Output is correct
3 Correct 25 ms 1900 KB Output is correct

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1900 KB Output is correct
2 Correct 27 ms 1900 KB Output is correct
3 Correct 25 ms 1900 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2028 KB Output is correct
2 Correct 27 ms 1900 KB Output is correct
3 Correct 25 ms 1900 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 2020 KB Output is correct
2 Correct 210 ms 1900 KB Output is correct
3 Correct 262 ms 1900 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 2020 KB Output is correct
2 Correct 366 ms 2032 KB Output is correct
3 Correct 321 ms 2020 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 1900 KB Output is correct
2 Correct 165 ms 1900 KB Output is correct
3 Correct 367 ms 1900 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 1900 KB Output is correct
2 Correct 269 ms 1972 KB Output is correct
3 Correct 245 ms 1900 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 2020 KB Output is correct
2 Correct 278 ms 2020 KB Output is correct
3 Correct 36 ms 2020 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 2020 KB Output is correct
2 Correct 31 ms 1900 KB Output is correct
3 Correct 174 ms 1968 KB Output is correct