#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
typedef long long ll;
const int N = 2e5+5;
ll n, k, cn, ans = -1e18;
ll root[N], lc[N*40], b[N], rc[N*40];
pair<ll, ll> tree[N*40];
vector<pair<ll, ll>> comp;
pair<ll, ll> p[N];
void merge(int node)
{
tree[node].f = tree[lc[node]].f+tree[rc[node]].f;
tree[node].s = tree[lc[node]].s+tree[rc[node]].s;
}
void build(int node = 0, int l=0, int r=n-1)
{
if(l == r)
{
tree[node] = {1, comp[l].f};
//cout << node << " " << tree[node].f << " " << tree[node].s << " | " << l << " " << r << endl;
return ;
}
int mid = (l+r)>>1;
lc[node] = ++cn, rc[node] = ++cn;
build(lc[node], l, mid);
build(rc[node], mid+1, r);
merge(node);
//cout << node << " " << tree[node].f << " " << tree[node].s << " | " << l << " " << r << endl;
}
void upd(int i, int node, int node2, int l=0, int r=n-1)
{
tree[node] = tree[node2];
if(l == r)
{
tree[node] = {0, 0};
//cout << node << " " << tree[node].f << " " << tree[node].s << " | " << l << " " << r << endl;
return ;
}
int mid = (l+r)>>1;
if(i > mid)
{
rc[node] = ++cn;
lc[node] = lc[node2];
upd(i, rc[node], rc[node2], mid+1, r);
}
else
{
rc[node] = rc[node2];
lc[node] = ++cn;
upd(i, lc[node], lc[node2], l, mid);
}
merge(node);
//cout << node << " " << tree[node].f << " " << tree[node].s << " | " << l << " " << r << endl;
}
bool cmp(pair<ll, ll> a, pair<ll, ll> b)
{
return a.s < b.s;
}
ll sum2(ll l, ll r)
{
vector<ll> vec;
ll ret = 0;
for(ll i=l; i<=r; i++)
{
vec.push_back(p[i].f);
}
sort(vec.rbegin(), vec.rend());
for(ll i=0; i<k; i++) ret += vec[i];
return ret;
}
ll sum(int node1, int node2, ll cnt)
{
ll cmt = tree[rc[node2]].f-tree[rc[node1]].f;
// cout << node1 << " " << node2 << " | " << rc[node1] << " " << lc[node1]
// << " | " << cmt << " " << cnt << " " << tree[node2].f-tree[node1].f << endl;
assert(tree[node2].f-tree[node1].f >= cnt);
if(tree[node2].f-tree[node1].f == cnt) return tree[node2].s-tree[node1].s;
if(!cnt) return 0;
else if(cmt >= cnt) return sum(rc[node1], rc[node2], cnt);
else return sum(rc[node1], rc[node2], cmt) + sum(lc[node1], lc[node2], cnt-cmt);
}
void solve(ll l, ll r, ll s, ll e)
{
if(l > r) return ;
ll id = -1, m = -1e18;
ll mid = (l+r)>>1;
for(ll i=max(mid+k-1, (ll)s); i<=e; i++)
{
ll tmp;
if(tree[root[mid]].f-tree[root[i+1]].f >= k) tmp = sum(root[i+1], root[mid], k);
else tmp = sum2(mid, i);
tmp -= (p[i].s-p[mid].s)*2LL;
if(tmp > m) m = tmp, id = i;
}
solve(l, mid-1, s, id);
solve(mid+1, r, id, e);
ans = max(ans, m);
}
int main()
{
cin >> n >> k;
for(int i=0; i<n; i++) scanf("%lld %lld", &p[i].f, &p[i].s);
sort(p, p+n, cmp);
for(int i=0; i<n; i++) comp.push_back({p[i].f, i});
sort(comp.begin(), comp.end());
for(int i=0; i<n; i++) b[comp[i].s] = i;
build();
for(int i=1; i<=n; i++)
{
int id = b[i-1];
root[i] = ++cn;
upd(id, root[i], root[i-1]);
}
//cout << sum(root[6+1], root[1], k) << " " << sum2(1, 6) << endl;
solve(0, n-k, 0, n-1);
cout << ans << endl;
}
Compilation message
cake3.cpp: In function 'int main()':
cake3.cpp:105:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<n; i++) scanf("%lld %lld", &p[i].f, &p[i].s);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
420 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
4 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
380 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
372 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
3 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
376 KB |
Output is correct |
36 |
Correct |
2 ms |
376 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
420 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
4 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
380 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
372 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
3 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
376 KB |
Output is correct |
36 |
Correct |
2 ms |
376 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
38 |
Correct |
5 ms |
1272 KB |
Output is correct |
39 |
Correct |
6 ms |
1400 KB |
Output is correct |
40 |
Correct |
5 ms |
1400 KB |
Output is correct |
41 |
Correct |
5 ms |
1272 KB |
Output is correct |
42 |
Correct |
5 ms |
1400 KB |
Output is correct |
43 |
Correct |
5 ms |
1272 KB |
Output is correct |
44 |
Correct |
5 ms |
1272 KB |
Output is correct |
45 |
Correct |
6 ms |
1400 KB |
Output is correct |
46 |
Correct |
6 ms |
1404 KB |
Output is correct |
47 |
Correct |
6 ms |
1272 KB |
Output is correct |
48 |
Correct |
5 ms |
1272 KB |
Output is correct |
49 |
Correct |
5 ms |
1528 KB |
Output is correct |
50 |
Correct |
5 ms |
1400 KB |
Output is correct |
51 |
Correct |
5 ms |
1400 KB |
Output is correct |
52 |
Correct |
5 ms |
1272 KB |
Output is correct |
53 |
Correct |
6 ms |
1276 KB |
Output is correct |
54 |
Correct |
5 ms |
1400 KB |
Output is correct |
55 |
Correct |
5 ms |
1400 KB |
Output is correct |
56 |
Correct |
4 ms |
1400 KB |
Output is correct |
57 |
Correct |
4 ms |
1272 KB |
Output is correct |
58 |
Correct |
5 ms |
1272 KB |
Output is correct |
59 |
Correct |
4 ms |
1272 KB |
Output is correct |
60 |
Correct |
5 ms |
1272 KB |
Output is correct |
61 |
Correct |
4 ms |
1272 KB |
Output is correct |
62 |
Correct |
4 ms |
1400 KB |
Output is correct |
63 |
Correct |
5 ms |
1404 KB |
Output is correct |
64 |
Correct |
4 ms |
1400 KB |
Output is correct |
65 |
Correct |
5 ms |
1272 KB |
Output is correct |
66 |
Correct |
5 ms |
1272 KB |
Output is correct |
67 |
Correct |
5 ms |
1400 KB |
Output is correct |
68 |
Correct |
5 ms |
1400 KB |
Output is correct |
69 |
Correct |
5 ms |
1400 KB |
Output is correct |
70 |
Correct |
5 ms |
1400 KB |
Output is correct |
71 |
Correct |
5 ms |
1400 KB |
Output is correct |
72 |
Correct |
4 ms |
1400 KB |
Output is correct |
73 |
Correct |
5 ms |
1400 KB |
Output is correct |
74 |
Correct |
4 ms |
1528 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
420 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
4 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
380 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
2 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
2 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
376 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
2 ms |
372 KB |
Output is correct |
21 |
Correct |
2 ms |
376 KB |
Output is correct |
22 |
Correct |
2 ms |
376 KB |
Output is correct |
23 |
Correct |
2 ms |
376 KB |
Output is correct |
24 |
Correct |
2 ms |
376 KB |
Output is correct |
25 |
Correct |
2 ms |
376 KB |
Output is correct |
26 |
Correct |
2 ms |
376 KB |
Output is correct |
27 |
Correct |
2 ms |
376 KB |
Output is correct |
28 |
Correct |
2 ms |
376 KB |
Output is correct |
29 |
Correct |
3 ms |
376 KB |
Output is correct |
30 |
Correct |
2 ms |
376 KB |
Output is correct |
31 |
Correct |
2 ms |
376 KB |
Output is correct |
32 |
Correct |
2 ms |
376 KB |
Output is correct |
33 |
Correct |
2 ms |
376 KB |
Output is correct |
34 |
Correct |
2 ms |
376 KB |
Output is correct |
35 |
Correct |
2 ms |
376 KB |
Output is correct |
36 |
Correct |
2 ms |
376 KB |
Output is correct |
37 |
Correct |
2 ms |
376 KB |
Output is correct |
38 |
Correct |
5 ms |
1272 KB |
Output is correct |
39 |
Correct |
6 ms |
1400 KB |
Output is correct |
40 |
Correct |
5 ms |
1400 KB |
Output is correct |
41 |
Correct |
5 ms |
1272 KB |
Output is correct |
42 |
Correct |
5 ms |
1400 KB |
Output is correct |
43 |
Correct |
5 ms |
1272 KB |
Output is correct |
44 |
Correct |
5 ms |
1272 KB |
Output is correct |
45 |
Correct |
6 ms |
1400 KB |
Output is correct |
46 |
Correct |
6 ms |
1404 KB |
Output is correct |
47 |
Correct |
6 ms |
1272 KB |
Output is correct |
48 |
Correct |
5 ms |
1272 KB |
Output is correct |
49 |
Correct |
5 ms |
1528 KB |
Output is correct |
50 |
Correct |
5 ms |
1400 KB |
Output is correct |
51 |
Correct |
5 ms |
1400 KB |
Output is correct |
52 |
Correct |
5 ms |
1272 KB |
Output is correct |
53 |
Correct |
6 ms |
1276 KB |
Output is correct |
54 |
Correct |
5 ms |
1400 KB |
Output is correct |
55 |
Correct |
5 ms |
1400 KB |
Output is correct |
56 |
Correct |
4 ms |
1400 KB |
Output is correct |
57 |
Correct |
4 ms |
1272 KB |
Output is correct |
58 |
Correct |
5 ms |
1272 KB |
Output is correct |
59 |
Correct |
4 ms |
1272 KB |
Output is correct |
60 |
Correct |
5 ms |
1272 KB |
Output is correct |
61 |
Correct |
4 ms |
1272 KB |
Output is correct |
62 |
Correct |
4 ms |
1400 KB |
Output is correct |
63 |
Correct |
5 ms |
1404 KB |
Output is correct |
64 |
Correct |
4 ms |
1400 KB |
Output is correct |
65 |
Correct |
5 ms |
1272 KB |
Output is correct |
66 |
Correct |
5 ms |
1272 KB |
Output is correct |
67 |
Correct |
5 ms |
1400 KB |
Output is correct |
68 |
Correct |
5 ms |
1400 KB |
Output is correct |
69 |
Correct |
5 ms |
1400 KB |
Output is correct |
70 |
Correct |
5 ms |
1400 KB |
Output is correct |
71 |
Correct |
5 ms |
1400 KB |
Output is correct |
72 |
Correct |
4 ms |
1400 KB |
Output is correct |
73 |
Correct |
5 ms |
1400 KB |
Output is correct |
74 |
Correct |
4 ms |
1528 KB |
Output is correct |
75 |
Correct |
1137 ms |
129560 KB |
Output is correct |
76 |
Correct |
1132 ms |
125940 KB |
Output is correct |
77 |
Correct |
1041 ms |
130200 KB |
Output is correct |
78 |
Correct |
1037 ms |
132224 KB |
Output is correct |
79 |
Correct |
372 ms |
132480 KB |
Output is correct |
80 |
Correct |
412 ms |
128476 KB |
Output is correct |
81 |
Correct |
921 ms |
131384 KB |
Output is correct |
82 |
Correct |
1106 ms |
133272 KB |
Output is correct |
83 |
Correct |
1044 ms |
137908 KB |
Output is correct |
84 |
Correct |
1206 ms |
137256 KB |
Output is correct |
85 |
Correct |
943 ms |
132504 KB |
Output is correct |
86 |
Correct |
590 ms |
127756 KB |
Output is correct |
87 |
Correct |
624 ms |
126172 KB |
Output is correct |
88 |
Correct |
880 ms |
125148 KB |
Output is correct |
89 |
Correct |
797 ms |
132572 KB |
Output is correct |
90 |
Correct |
632 ms |
138844 KB |
Output is correct |
91 |
Correct |
466 ms |
127964 KB |
Output is correct |
92 |
Correct |
476 ms |
126944 KB |
Output is correct |
93 |
Correct |
538 ms |
132700 KB |
Output is correct |
94 |
Correct |
459 ms |
138796 KB |
Output is correct |
95 |
Correct |
597 ms |
138984 KB |
Output is correct |
96 |
Correct |
448 ms |
128732 KB |
Output is correct |
97 |
Correct |
464 ms |
139356 KB |
Output is correct |
98 |
Correct |
487 ms |
137052 KB |
Output is correct |
99 |
Correct |
458 ms |
137420 KB |
Output is correct |
100 |
Correct |
382 ms |
129244 KB |
Output is correct |
101 |
Correct |
390 ms |
129116 KB |
Output is correct |
102 |
Correct |
920 ms |
129368 KB |
Output is correct |
103 |
Correct |
858 ms |
127456 KB |
Output is correct |
104 |
Correct |
1002 ms |
134748 KB |
Output is correct |
105 |
Correct |
875 ms |
134256 KB |
Output is correct |
106 |
Correct |
853 ms |
137888 KB |
Output is correct |
107 |
Correct |
725 ms |
133128 KB |
Output is correct |
108 |
Correct |
958 ms |
131784 KB |
Output is correct |
109 |
Correct |
856 ms |
140380 KB |
Output is correct |
110 |
Correct |
423 ms |
130816 KB |
Output is correct |
111 |
Correct |
532 ms |
132316 KB |
Output is correct |
112 |
Correct |
998 ms |
126180 KB |
Output is correct |
113 |
Correct |
386 ms |
140132 KB |
Output is correct |