oj.uz

Submission #321332

# Submission time Handle Problem Language Result Execution time Memory
321332 2020-11-12T06:13:48 Z shivensinha4 Simfonija (COCI19_simfonija) C++17
99 / 110
 307 ms 3684 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];
	}
	
	vector<ll> offset = nums;
	for_(i, 0, n) offset[i] = -offset[i];
	reverse(offset.begin(), offset.end());
	
	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 = n-end-1, r = n-st-1;
		while (r-l >= 3) {
			ll m1 = l + (r-l) / 3, m2 = r - (r-l) / 3;
			if (f(offset[m1], st, end) < f(offset[m2], st, end)) l = m1;
			else r = m2;
		}
		
		ll rem = 0;
		for_(i, l, r+1) rem = max(rem, f(offset[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 32 ms 3300 KB Output is correct
2 Correct 28 ms 3300 KB Output is correct
3 Correct 27 ms 3300 KB Output is correct

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3304 KB Output is correct
2 Correct 29 ms 3304 KB Output is correct
3 Incorrect 26 ms 3296 KB Output isn't correct

Subtask #4
11.0 / 11.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 3300 KB Output is correct
2 Correct 176 ms 3356 KB Output is correct
3 Correct 233 ms 3556 KB Output is correct

Subtask #6
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 3300 KB Output is correct
2 Correct 307 ms 3356 KB Output is correct
3 Correct 282 ms 3684 KB Output is correct

Subtask #7
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 3308 KB Output is correct
2 Correct 153 ms 3300 KB Output is correct
3 Correct 306 ms 3300 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 293 ms 3428 KB Output is correct
2 Correct 224 ms 3428 KB Output is correct
3 Correct 222 ms 3556 KB Output is correct

Subtask #9
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 3304 KB Output is correct
2 Correct 210 ms 3308 KB Output is correct
3 Correct 36 ms 3556 KB Output is correct

Subtask #10
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 3300 KB Output is correct
2 Correct 27 ms 3304 KB Output is correct
3 Correct 169 ms 3428 KB Output is correct