1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <cstdio>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 5e5 + 10;
LL ans;
int n, m, cnt, A[N], B[N];
void check(LL x)
{
cnt = ans = 0;
priority_queue<PLI, vector<PLI>, greater<PLI>> q;
for (int i = 1; i <= n; i++)
{
q.push(make_pair(A[i] - x, 1));
PLI t = q.top();
if (B[i] + t.first >= 0)
continue;
q.pop();
cnt += t.second;
ans += B[i] + t.first;
q.push(make_pair(-B[i], 0));
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &A[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &B[i]);
LL l = 0, r = 2e9, res;
while (l <= r)
{
LL mid = l + r >> 1;
check(mid);
cnt <= m ? (res = ans + (LL)mid * m, l = mid + 1) : r = mid - 1;
}
printf("%lld", res);
return 0;
}
|
