# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
112557 |
2019-05-20T14:32:05 Z |
someone_aa |
Cake 3 (JOI19_cake3) |
C++17 |
|
2044 ms |
226908 KB |
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define P pair<ll,ll>
using namespace std;
const int maxn = 200100;
ll n, m, arr[maxn];
vector<P>v;
struct node {
public:
node *lc, *rc;
ll cnt;
ll sum;
node(ll _cnt, ll _sum) {
lc = rc = NULL;
cnt = _cnt; sum = _sum;
}
node(node *a, node *b) {
sum = a->sum + b->sum;
cnt = a->cnt + b->cnt;
lc = a;
rc = b;
}
};
ll val[maxn], result;
set<ll>st;
map<ll,int>ind;
node* pref[maxn];
node* build(int li=0, int ri=n) {
if(li == ri) return new node(0LL, 0LL);
else {
int mid = (li + ri) / 2;
return new node(build(li, mid), build(mid+1, ri));
}
}
node* insert_number(node *curr, int pos, int sum_val, int li=0, int ri=n) {
if(li == ri) {
return new node(curr->cnt+1, curr->sum+sum_val);
}
else {
int mid = (li + ri) / 2;
if(pos <= mid)
return new node(insert_number(curr->lc, pos, sum_val, li, mid), curr->rc);
else
return new node(curr->lc, insert_number(curr->rc, pos, sum_val, mid+1, ri));
}
}
ll solve(node *l, node *r, int k, int li=0, int ri=n) {
if(k == 0) return 0LL;
ll total_cnt = r->cnt - l->cnt;
ll total_sum = r->sum - l->sum;
//cout<<"["<<li<<" "<<ri<<"] -> "<<total_cnt<<", "<<total_sum<<"\n";
if(k == total_cnt) return total_sum;
if(li == ri) return k * val[li];
else {
int mid = (li + ri) / 2;
ll total = r -> rc -> cnt - l -> rc -> cnt;
ll sum_total = r -> rc -> sum - l -> rc -> sum;
if(total >= k) return solve(l->rc, r->rc, k, mid+1, ri);
else return sum_total + solve(l->lc, r->lc, k-total, li, mid);
}
}
// i < j
ll f(int i, int j) {
if(i >= j) return LLONG_MIN;
if(j - i + 1 < m) return LLONG_MIN;
ll sum = v[i-1].second + v[j-1].second;
ll cost = 2*(v[j-1].first - v[i-1].first);
return solve(pref[i], pref[j-1], m-2) + sum - cost;
}
void fsolve(int l, int r, int optl, int optr) {
if(l > r) return;
int mid = (l + r) / 2;
ll temp_cost = LLONG_MIN;
ll temp_ind = -1;
if(n - mid + 1 < m) {
temp_ind = n;
}
else {
for(int i=max(mid, optl);i<=optr;i++) {
ll temp = f(mid, i);
if(temp > temp_cost) {
temp_cost = temp;
temp_ind = i;
}
}
}
result = max(result, temp_cost);
fsolve(l, mid-1, optl, temp_ind);
fsolve(mid+1,r, temp_ind, optr);
}
int main() {
cin>>n>>m;
ll a, b;
for(int i=0;i<n;i++) {
cin>>a>>b;
v.pb(mp(b, a));
st.insert(a);
}
sort(v.begin(), v.end());
int br = 0;
for(ll i:st) {
val[br] = i;
ind[i] = br++;
}
node *root = build();
for(int i=1;i<=n;i++) {
root = insert_number(root, ind[v[i-1].second], v[i-1].second);
pref[i] = root;
}
result = LLONG_MIN;
fsolve(1, n, 1, n);
cout<<result<<"\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
384 KB |
Output is correct |
23 |
Correct |
2 ms |
384 KB |
Output is correct |
24 |
Correct |
2 ms |
384 KB |
Output is correct |
25 |
Correct |
2 ms |
384 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
2 ms |
384 KB |
Output is correct |
28 |
Correct |
3 ms |
384 KB |
Output is correct |
29 |
Correct |
2 ms |
384 KB |
Output is correct |
30 |
Correct |
2 ms |
384 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
2 ms |
384 KB |
Output is correct |
34 |
Correct |
2 ms |
512 KB |
Output is correct |
35 |
Correct |
2 ms |
384 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
384 KB |
Output is correct |
23 |
Correct |
2 ms |
384 KB |
Output is correct |
24 |
Correct |
2 ms |
384 KB |
Output is correct |
25 |
Correct |
2 ms |
384 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
2 ms |
384 KB |
Output is correct |
28 |
Correct |
3 ms |
384 KB |
Output is correct |
29 |
Correct |
2 ms |
384 KB |
Output is correct |
30 |
Correct |
2 ms |
384 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
2 ms |
384 KB |
Output is correct |
34 |
Correct |
2 ms |
512 KB |
Output is correct |
35 |
Correct |
2 ms |
384 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
2 ms |
384 KB |
Output is correct |
38 |
Correct |
8 ms |
1764 KB |
Output is correct |
39 |
Correct |
8 ms |
1920 KB |
Output is correct |
40 |
Correct |
7 ms |
1792 KB |
Output is correct |
41 |
Correct |
7 ms |
1792 KB |
Output is correct |
42 |
Correct |
6 ms |
1920 KB |
Output is correct |
43 |
Correct |
6 ms |
1792 KB |
Output is correct |
44 |
Correct |
7 ms |
1792 KB |
Output is correct |
45 |
Correct |
7 ms |
1920 KB |
Output is correct |
46 |
Correct |
7 ms |
1920 KB |
Output is correct |
47 |
Correct |
7 ms |
1792 KB |
Output is correct |
48 |
Correct |
7 ms |
1792 KB |
Output is correct |
49 |
Correct |
7 ms |
1920 KB |
Output is correct |
50 |
Correct |
7 ms |
1920 KB |
Output is correct |
51 |
Correct |
7 ms |
1920 KB |
Output is correct |
52 |
Correct |
7 ms |
1920 KB |
Output is correct |
53 |
Correct |
7 ms |
1920 KB |
Output is correct |
54 |
Correct |
6 ms |
1920 KB |
Output is correct |
55 |
Correct |
7 ms |
1920 KB |
Output is correct |
56 |
Correct |
6 ms |
1920 KB |
Output is correct |
57 |
Correct |
6 ms |
1792 KB |
Output is correct |
58 |
Correct |
6 ms |
1792 KB |
Output is correct |
59 |
Correct |
5 ms |
1536 KB |
Output is correct |
60 |
Correct |
5 ms |
1664 KB |
Output is correct |
61 |
Correct |
6 ms |
1664 KB |
Output is correct |
62 |
Correct |
5 ms |
1664 KB |
Output is correct |
63 |
Correct |
5 ms |
1664 KB |
Output is correct |
64 |
Correct |
5 ms |
1664 KB |
Output is correct |
65 |
Correct |
8 ms |
1920 KB |
Output is correct |
66 |
Correct |
7 ms |
1792 KB |
Output is correct |
67 |
Correct |
7 ms |
1920 KB |
Output is correct |
68 |
Correct |
7 ms |
1920 KB |
Output is correct |
69 |
Correct |
6 ms |
1792 KB |
Output is correct |
70 |
Correct |
7 ms |
1832 KB |
Output is correct |
71 |
Correct |
5 ms |
1664 KB |
Output is correct |
72 |
Correct |
5 ms |
1664 KB |
Output is correct |
73 |
Correct |
7 ms |
1792 KB |
Output is correct |
74 |
Correct |
7 ms |
1920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
2 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
384 KB |
Output is correct |
9 |
Correct |
2 ms |
384 KB |
Output is correct |
10 |
Correct |
2 ms |
384 KB |
Output is correct |
11 |
Correct |
2 ms |
384 KB |
Output is correct |
12 |
Correct |
2 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
384 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
2 ms |
384 KB |
Output is correct |
22 |
Correct |
2 ms |
384 KB |
Output is correct |
23 |
Correct |
2 ms |
384 KB |
Output is correct |
24 |
Correct |
2 ms |
384 KB |
Output is correct |
25 |
Correct |
2 ms |
384 KB |
Output is correct |
26 |
Correct |
2 ms |
384 KB |
Output is correct |
27 |
Correct |
2 ms |
384 KB |
Output is correct |
28 |
Correct |
3 ms |
384 KB |
Output is correct |
29 |
Correct |
2 ms |
384 KB |
Output is correct |
30 |
Correct |
2 ms |
384 KB |
Output is correct |
31 |
Correct |
2 ms |
384 KB |
Output is correct |
32 |
Correct |
2 ms |
384 KB |
Output is correct |
33 |
Correct |
2 ms |
384 KB |
Output is correct |
34 |
Correct |
2 ms |
512 KB |
Output is correct |
35 |
Correct |
2 ms |
384 KB |
Output is correct |
36 |
Correct |
2 ms |
384 KB |
Output is correct |
37 |
Correct |
2 ms |
384 KB |
Output is correct |
38 |
Correct |
8 ms |
1764 KB |
Output is correct |
39 |
Correct |
8 ms |
1920 KB |
Output is correct |
40 |
Correct |
7 ms |
1792 KB |
Output is correct |
41 |
Correct |
7 ms |
1792 KB |
Output is correct |
42 |
Correct |
6 ms |
1920 KB |
Output is correct |
43 |
Correct |
6 ms |
1792 KB |
Output is correct |
44 |
Correct |
7 ms |
1792 KB |
Output is correct |
45 |
Correct |
7 ms |
1920 KB |
Output is correct |
46 |
Correct |
7 ms |
1920 KB |
Output is correct |
47 |
Correct |
7 ms |
1792 KB |
Output is correct |
48 |
Correct |
7 ms |
1792 KB |
Output is correct |
49 |
Correct |
7 ms |
1920 KB |
Output is correct |
50 |
Correct |
7 ms |
1920 KB |
Output is correct |
51 |
Correct |
7 ms |
1920 KB |
Output is correct |
52 |
Correct |
7 ms |
1920 KB |
Output is correct |
53 |
Correct |
7 ms |
1920 KB |
Output is correct |
54 |
Correct |
6 ms |
1920 KB |
Output is correct |
55 |
Correct |
7 ms |
1920 KB |
Output is correct |
56 |
Correct |
6 ms |
1920 KB |
Output is correct |
57 |
Correct |
6 ms |
1792 KB |
Output is correct |
58 |
Correct |
6 ms |
1792 KB |
Output is correct |
59 |
Correct |
5 ms |
1536 KB |
Output is correct |
60 |
Correct |
5 ms |
1664 KB |
Output is correct |
61 |
Correct |
6 ms |
1664 KB |
Output is correct |
62 |
Correct |
5 ms |
1664 KB |
Output is correct |
63 |
Correct |
5 ms |
1664 KB |
Output is correct |
64 |
Correct |
5 ms |
1664 KB |
Output is correct |
65 |
Correct |
8 ms |
1920 KB |
Output is correct |
66 |
Correct |
7 ms |
1792 KB |
Output is correct |
67 |
Correct |
7 ms |
1920 KB |
Output is correct |
68 |
Correct |
7 ms |
1920 KB |
Output is correct |
69 |
Correct |
6 ms |
1792 KB |
Output is correct |
70 |
Correct |
7 ms |
1832 KB |
Output is correct |
71 |
Correct |
5 ms |
1664 KB |
Output is correct |
72 |
Correct |
5 ms |
1664 KB |
Output is correct |
73 |
Correct |
7 ms |
1792 KB |
Output is correct |
74 |
Correct |
7 ms |
1920 KB |
Output is correct |
75 |
Correct |
2044 ms |
206840 KB |
Output is correct |
76 |
Correct |
1971 ms |
204540 KB |
Output is correct |
77 |
Correct |
1901 ms |
211040 KB |
Output is correct |
78 |
Correct |
1952 ms |
214364 KB |
Output is correct |
79 |
Correct |
1160 ms |
215132 KB |
Output is correct |
80 |
Correct |
1224 ms |
208860 KB |
Output is correct |
81 |
Correct |
1275 ms |
193424 KB |
Output is correct |
82 |
Correct |
1581 ms |
198456 KB |
Output is correct |
83 |
Correct |
1319 ms |
203228 KB |
Output is correct |
84 |
Correct |
1419 ms |
203164 KB |
Output is correct |
85 |
Correct |
1185 ms |
195164 KB |
Output is correct |
86 |
Correct |
808 ms |
187244 KB |
Output is correct |
87 |
Correct |
864 ms |
184976 KB |
Output is correct |
88 |
Correct |
1088 ms |
184240 KB |
Output is correct |
89 |
Correct |
1055 ms |
194436 KB |
Output is correct |
90 |
Correct |
892 ms |
203356 KB |
Output is correct |
91 |
Correct |
711 ms |
187100 KB |
Output is correct |
92 |
Correct |
755 ms |
185556 KB |
Output is correct |
93 |
Correct |
799 ms |
193880 KB |
Output is correct |
94 |
Correct |
728 ms |
202456 KB |
Output is correct |
95 |
Correct |
875 ms |
203360 KB |
Output is correct |
96 |
Correct |
639 ms |
189916 KB |
Output is correct |
97 |
Correct |
672 ms |
204852 KB |
Output is correct |
98 |
Correct |
708 ms |
202012 KB |
Output is correct |
99 |
Correct |
639 ms |
202256 KB |
Output is correct |
100 |
Correct |
583 ms |
190812 KB |
Output is correct |
101 |
Correct |
591 ms |
190684 KB |
Output is correct |
102 |
Correct |
997 ms |
187716 KB |
Output is correct |
103 |
Correct |
1087 ms |
184916 KB |
Output is correct |
104 |
Correct |
1258 ms |
195676 KB |
Output is correct |
105 |
Correct |
945 ms |
194884 KB |
Output is correct |
106 |
Correct |
986 ms |
200156 KB |
Output is correct |
107 |
Correct |
753 ms |
192704 KB |
Output is correct |
108 |
Correct |
1839 ms |
213212 KB |
Output is correct |
109 |
Correct |
1780 ms |
226752 KB |
Output is correct |
110 |
Correct |
575 ms |
188788 KB |
Output is correct |
111 |
Correct |
657 ms |
190940 KB |
Output is correct |
112 |
Correct |
1335 ms |
202228 KB |
Output is correct |
113 |
Correct |
1270 ms |
226908 KB |
Output is correct |