# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
112558 |
2019-05-20T14:33:24 Z |
someone_aa |
Cake 3 (JOI19_cake3) |
C++17 |
|
1800 ms |
222940 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() {
ios_base::sync_with_stdio(false);
cin.tie(0);
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 |
3 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 |
0 ms |
380 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 |
384 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 |
512 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 |
2 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 |
7 ms |
384 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 |
3 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 |
0 ms |
380 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 |
384 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 |
512 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 |
2 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 |
7 ms |
384 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 |
7 ms |
1792 KB |
Output is correct |
39 |
Correct |
7 ms |
1920 KB |
Output is correct |
40 |
Correct |
6 ms |
1920 KB |
Output is correct |
41 |
Correct |
6 ms |
1920 KB |
Output is correct |
42 |
Correct |
10 ms |
2048 KB |
Output is correct |
43 |
Correct |
5 ms |
1792 KB |
Output is correct |
44 |
Correct |
6 ms |
1920 KB |
Output is correct |
45 |
Correct |
7 ms |
1992 KB |
Output is correct |
46 |
Correct |
7 ms |
1920 KB |
Output is correct |
47 |
Correct |
7 ms |
1992 KB |
Output is correct |
48 |
Correct |
6 ms |
1792 KB |
Output is correct |
49 |
Correct |
6 ms |
1920 KB |
Output is correct |
50 |
Correct |
6 ms |
1920 KB |
Output is correct |
51 |
Correct |
6 ms |
1920 KB |
Output is correct |
52 |
Correct |
6 ms |
1920 KB |
Output is correct |
53 |
Correct |
6 ms |
1920 KB |
Output is correct |
54 |
Correct |
6 ms |
1920 KB |
Output is correct |
55 |
Correct |
5 ms |
1920 KB |
Output is correct |
56 |
Correct |
6 ms |
1920 KB |
Output is correct |
57 |
Correct |
5 ms |
1920 KB |
Output is correct |
58 |
Correct |
6 ms |
1792 KB |
Output is correct |
59 |
Correct |
4 ms |
1664 KB |
Output is correct |
60 |
Correct |
4 ms |
1664 KB |
Output is correct |
61 |
Correct |
5 ms |
1664 KB |
Output is correct |
62 |
Correct |
5 ms |
1792 KB |
Output is correct |
63 |
Correct |
4 ms |
1664 KB |
Output is correct |
64 |
Correct |
5 ms |
1792 KB |
Output is correct |
65 |
Correct |
6 ms |
1920 KB |
Output is correct |
66 |
Correct |
6 ms |
1792 KB |
Output is correct |
67 |
Correct |
6 ms |
1920 KB |
Output is correct |
68 |
Correct |
6 ms |
1920 KB |
Output is correct |
69 |
Correct |
6 ms |
1920 KB |
Output is correct |
70 |
Correct |
5 ms |
1920 KB |
Output is correct |
71 |
Correct |
4 ms |
1664 KB |
Output is correct |
72 |
Correct |
4 ms |
1792 KB |
Output is correct |
73 |
Correct |
6 ms |
1920 KB |
Output is correct |
74 |
Correct |
6 ms |
2048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 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 |
0 ms |
380 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 |
384 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 |
512 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 |
2 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 |
7 ms |
384 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 |
7 ms |
1792 KB |
Output is correct |
39 |
Correct |
7 ms |
1920 KB |
Output is correct |
40 |
Correct |
6 ms |
1920 KB |
Output is correct |
41 |
Correct |
6 ms |
1920 KB |
Output is correct |
42 |
Correct |
10 ms |
2048 KB |
Output is correct |
43 |
Correct |
5 ms |
1792 KB |
Output is correct |
44 |
Correct |
6 ms |
1920 KB |
Output is correct |
45 |
Correct |
7 ms |
1992 KB |
Output is correct |
46 |
Correct |
7 ms |
1920 KB |
Output is correct |
47 |
Correct |
7 ms |
1992 KB |
Output is correct |
48 |
Correct |
6 ms |
1792 KB |
Output is correct |
49 |
Correct |
6 ms |
1920 KB |
Output is correct |
50 |
Correct |
6 ms |
1920 KB |
Output is correct |
51 |
Correct |
6 ms |
1920 KB |
Output is correct |
52 |
Correct |
6 ms |
1920 KB |
Output is correct |
53 |
Correct |
6 ms |
1920 KB |
Output is correct |
54 |
Correct |
6 ms |
1920 KB |
Output is correct |
55 |
Correct |
5 ms |
1920 KB |
Output is correct |
56 |
Correct |
6 ms |
1920 KB |
Output is correct |
57 |
Correct |
5 ms |
1920 KB |
Output is correct |
58 |
Correct |
6 ms |
1792 KB |
Output is correct |
59 |
Correct |
4 ms |
1664 KB |
Output is correct |
60 |
Correct |
4 ms |
1664 KB |
Output is correct |
61 |
Correct |
5 ms |
1664 KB |
Output is correct |
62 |
Correct |
5 ms |
1792 KB |
Output is correct |
63 |
Correct |
4 ms |
1664 KB |
Output is correct |
64 |
Correct |
5 ms |
1792 KB |
Output is correct |
65 |
Correct |
6 ms |
1920 KB |
Output is correct |
66 |
Correct |
6 ms |
1792 KB |
Output is correct |
67 |
Correct |
6 ms |
1920 KB |
Output is correct |
68 |
Correct |
6 ms |
1920 KB |
Output is correct |
69 |
Correct |
6 ms |
1920 KB |
Output is correct |
70 |
Correct |
5 ms |
1920 KB |
Output is correct |
71 |
Correct |
4 ms |
1664 KB |
Output is correct |
72 |
Correct |
4 ms |
1792 KB |
Output is correct |
73 |
Correct |
6 ms |
1920 KB |
Output is correct |
74 |
Correct |
6 ms |
2048 KB |
Output is correct |
75 |
Correct |
1788 ms |
206988 KB |
Output is correct |
76 |
Correct |
1800 ms |
201064 KB |
Output is correct |
77 |
Correct |
1706 ms |
207904 KB |
Output is correct |
78 |
Correct |
1780 ms |
211036 KB |
Output is correct |
79 |
Correct |
1074 ms |
211804 KB |
Output is correct |
80 |
Correct |
1111 ms |
205368 KB |
Output is correct |
81 |
Correct |
1121 ms |
190688 KB |
Output is correct |
82 |
Correct |
1422 ms |
195604 KB |
Output is correct |
83 |
Correct |
1286 ms |
200524 KB |
Output is correct |
84 |
Correct |
1317 ms |
200284 KB |
Output is correct |
85 |
Correct |
1157 ms |
192348 KB |
Output is correct |
86 |
Correct |
753 ms |
184796 KB |
Output is correct |
87 |
Correct |
823 ms |
182328 KB |
Output is correct |
88 |
Correct |
1079 ms |
181712 KB |
Output is correct |
89 |
Correct |
1049 ms |
191744 KB |
Output is correct |
90 |
Correct |
797 ms |
200280 KB |
Output is correct |
91 |
Correct |
799 ms |
184356 KB |
Output is correct |
92 |
Correct |
704 ms |
183144 KB |
Output is correct |
93 |
Correct |
764 ms |
191160 KB |
Output is correct |
94 |
Correct |
622 ms |
199564 KB |
Output is correct |
95 |
Correct |
840 ms |
200516 KB |
Output is correct |
96 |
Correct |
549 ms |
187104 KB |
Output is correct |
97 |
Correct |
604 ms |
201952 KB |
Output is correct |
98 |
Correct |
606 ms |
198968 KB |
Output is correct |
99 |
Correct |
562 ms |
199428 KB |
Output is correct |
100 |
Correct |
502 ms |
188004 KB |
Output is correct |
101 |
Correct |
508 ms |
188108 KB |
Output is correct |
102 |
Correct |
980 ms |
185000 KB |
Output is correct |
103 |
Correct |
863 ms |
182364 KB |
Output is correct |
104 |
Correct |
1146 ms |
192988 KB |
Output is correct |
105 |
Correct |
865 ms |
192076 KB |
Output is correct |
106 |
Correct |
881 ms |
197304 KB |
Output is correct |
107 |
Correct |
705 ms |
189988 KB |
Output is correct |
108 |
Correct |
1757 ms |
209696 KB |
Output is correct |
109 |
Correct |
1668 ms |
222940 KB |
Output is correct |
110 |
Correct |
469 ms |
186720 KB |
Output is correct |
111 |
Correct |
584 ms |
188768 KB |
Output is correct |
112 |
Correct |
1259 ms |
200156 KB |
Output is correct |
113 |
Correct |
1043 ms |
222940 KB |
Output is correct |