#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 = ans - (posRem > 0 ? sufPos[n-posRem] : 0) - (negRem > 0 ? sufNeg[n-negRem] : 0);
// cout << curr << 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?
}
ans = min(ans, curr);
negRem -= 1; posRem += 1;
}
cout << ans << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
0 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
5208 KB |
Output is correct |
| 2 |
Correct |
31 ms |
5228 KB |
Output is correct |
| 3 |
Correct |
30 ms |
5088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
5208 KB |
Output is correct |
| 2 |
Correct |
31 ms |
5216 KB |
Output is correct |
| 3 |
Correct |
28 ms |
5336 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
5208 KB |
Output is correct |
| 2 |
Correct |
33 ms |
5208 KB |
Output is correct |
| 3 |
Correct |
29 ms |
5084 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
5216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
5356 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
10448 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
5216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
35 ms |
5216 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
5268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
