# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
202405 |
2020-02-16T03:47:32 Z |
Rakhmand |
Cake 3 (JOI19_cake3) |
C++14 |
|
581 ms |
262148 KB |
//
// ROIGold.cpp
// Main calisma
//
// Created by Rakhman on 05/02/2019.
// Copyright © 2019 Rakhman. All rights reserved.
//
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>
#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(llong i = start; i <= finish; i += k)
const long long MXN = 2e5 + 10;
const long long MNN = 1e6 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e16;
const long long OO = 1e9 + 10;
typedef long long llong;
typedef unsigned long long ullong;
using namespace std;
void istxt(bool yes){
if(yes == 1){
freopen("balancing.in", "r", stdin);
freopen("balancing.out", "w", stdout);
}else{
freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
}
}
llong n, m;
pair<llong, llong> p[MXN];
vector<llong> c;
llong find_pos(llong x) { return (lower_bound(c.begin(), c.end(), x) - c.begin()); }
struct node{
node *l, *r;
llong cnt;
llong sum;
node(){
l = r = nullptr;
cnt = sum = 0;
}
};
typedef node* pnode;
pnode t[MXN];
llong getcnt(pnode x) {return (x == nullptr ? 0 : x -> cnt); }
llong getsum(pnode x) { return (x == nullptr ? 0 : x -> sum); }
pnode upd(pnode last, llong pos, llong tl = 0, llong tr = c.size() - 1){
pnode cur = new node();
if(tl == tr){
cur -> sum = getsum(last) + c[pos];
cur -> cnt = getcnt(last) + 1;
return cur;
}
llong tm = (tl + tr) / 2;
if(pos <= tm){
cur -> l = new node();
if(last != nullptr){
cur -> l = upd(last -> l, pos, tl, tm);
cur -> r = last -> r;
}else{
cur -> l = upd(nullptr, pos, tl, tm);
cur -> r = nullptr;
}
}else{
cur -> r = new node();
if(last != nullptr){
cur -> l = last -> l;
cur -> r = upd(last -> r, pos, tm + 1, tr);
}else{
cur -> l = nullptr;
cur -> r = upd(nullptr, pos, tm + 1, tr);
}
}
cur -> sum = getsum(cur->l) + getsum(cur->r);
cur -> cnt = getcnt(cur->l) + getcnt(cur->r);
return cur;
}
llong get(pnode v, pnode last, llong k, llong tl = 0, llong tr = c.size() - 1){
if(k == 0) return 0;
if(tl == tr) {
if(v == nullptr) return 0;
llong x = v -> sum / v -> cnt;
return x * k;
}
llong right = 0;
if(v != nullptr) right = getcnt(v -> r);
if(last != nullptr) right -= getcnt(last -> r);
llong tm = (tl + tr) / 2;
if(right < k){
llong sum = 0;
if(v != nullptr) sum += getsum(v -> r);
if(last != nullptr) sum -= getsum(last -> r);
return sum + get((v == nullptr ? nullptr : v -> l), (last == nullptr ? nullptr : last -> l), k - right, tl, tm);
}else{
return get((v == nullptr ? nullptr : v -> r), (last == nullptr ? nullptr : last -> r), k, tm + 1, tr);
}
}
int main () {
ios;
//istxt(0);
cin >> n >> m;
for(llong i = 1; i <= n; i++){
cin >> p[i].S >> p[i].F;
c.push_back(p[i].S);
}
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
sort(p + 1, p + n + 1);
t[0] = new node();
for(llong i = 1; i <= n; i++){
t[i] = upd(t[i - 1], find_pos(p[i].S));
}
llong ans = -INF;
for(llong i = 1; i <= n; i++){
for(llong j = i + m - 1; j <= n; j++){
ans = max(ans, get(t[j], t[i - 1], m) - 2 * (p[j].F - p[i].F));
}
}
cout << ans;
}
Compilation message
cake3.cpp: In function 'void istxt(bool)':
cake3.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("balancing.in", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("balancing.out", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cake3.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
380 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
380 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
408 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
6 ms |
376 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
504 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
5 ms |
376 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
376 KB |
Output is correct |
25 |
Correct |
5 ms |
376 KB |
Output is correct |
26 |
Correct |
6 ms |
376 KB |
Output is correct |
27 |
Correct |
5 ms |
376 KB |
Output is correct |
28 |
Correct |
5 ms |
376 KB |
Output is correct |
29 |
Correct |
5 ms |
376 KB |
Output is correct |
30 |
Correct |
5 ms |
504 KB |
Output is correct |
31 |
Correct |
5 ms |
380 KB |
Output is correct |
32 |
Correct |
5 ms |
376 KB |
Output is correct |
33 |
Correct |
5 ms |
376 KB |
Output is correct |
34 |
Correct |
5 ms |
376 KB |
Output is correct |
35 |
Correct |
5 ms |
380 KB |
Output is correct |
36 |
Correct |
5 ms |
376 KB |
Output is correct |
37 |
Correct |
5 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
380 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
380 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
408 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
6 ms |
376 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
504 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
5 ms |
376 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
376 KB |
Output is correct |
25 |
Correct |
5 ms |
376 KB |
Output is correct |
26 |
Correct |
6 ms |
376 KB |
Output is correct |
27 |
Correct |
5 ms |
376 KB |
Output is correct |
28 |
Correct |
5 ms |
376 KB |
Output is correct |
29 |
Correct |
5 ms |
376 KB |
Output is correct |
30 |
Correct |
5 ms |
504 KB |
Output is correct |
31 |
Correct |
5 ms |
380 KB |
Output is correct |
32 |
Correct |
5 ms |
376 KB |
Output is correct |
33 |
Correct |
5 ms |
376 KB |
Output is correct |
34 |
Correct |
5 ms |
376 KB |
Output is correct |
35 |
Correct |
5 ms |
380 KB |
Output is correct |
36 |
Correct |
5 ms |
376 KB |
Output is correct |
37 |
Correct |
5 ms |
376 KB |
Output is correct |
38 |
Correct |
80 ms |
2424 KB |
Output is correct |
39 |
Correct |
82 ms |
2552 KB |
Output is correct |
40 |
Correct |
35 ms |
2424 KB |
Output is correct |
41 |
Correct |
40 ms |
2420 KB |
Output is correct |
42 |
Correct |
18 ms |
2552 KB |
Output is correct |
43 |
Correct |
25 ms |
2412 KB |
Output is correct |
44 |
Correct |
65 ms |
2424 KB |
Output is correct |
45 |
Correct |
76 ms |
2552 KB |
Output is correct |
46 |
Correct |
85 ms |
2552 KB |
Output is correct |
47 |
Correct |
94 ms |
2424 KB |
Output is correct |
48 |
Correct |
78 ms |
2424 KB |
Output is correct |
49 |
Correct |
55 ms |
2680 KB |
Output is correct |
50 |
Correct |
56 ms |
2552 KB |
Output is correct |
51 |
Correct |
50 ms |
2552 KB |
Output is correct |
52 |
Correct |
44 ms |
2424 KB |
Output is correct |
53 |
Correct |
49 ms |
2552 KB |
Output is correct |
54 |
Correct |
26 ms |
2552 KB |
Output is correct |
55 |
Correct |
18 ms |
2424 KB |
Output is correct |
56 |
Correct |
17 ms |
2424 KB |
Output is correct |
57 |
Correct |
21 ms |
2424 KB |
Output is correct |
58 |
Correct |
18 ms |
2424 KB |
Output is correct |
59 |
Correct |
12 ms |
504 KB |
Output is correct |
60 |
Correct |
15 ms |
760 KB |
Output is correct |
61 |
Correct |
12 ms |
504 KB |
Output is correct |
62 |
Correct |
11 ms |
508 KB |
Output is correct |
63 |
Correct |
10 ms |
760 KB |
Output is correct |
64 |
Correct |
11 ms |
504 KB |
Output is correct |
65 |
Correct |
71 ms |
2424 KB |
Output is correct |
66 |
Correct |
62 ms |
2424 KB |
Output is correct |
67 |
Correct |
81 ms |
2680 KB |
Output is correct |
68 |
Correct |
55 ms |
2552 KB |
Output is correct |
69 |
Correct |
44 ms |
2424 KB |
Output is correct |
70 |
Correct |
48 ms |
2552 KB |
Output is correct |
71 |
Correct |
26 ms |
1144 KB |
Output is correct |
72 |
Correct |
12 ms |
1144 KB |
Output is correct |
73 |
Correct |
76 ms |
2424 KB |
Output is correct |
74 |
Correct |
8 ms |
2552 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
380 KB |
Output is correct |
2 |
Correct |
5 ms |
376 KB |
Output is correct |
3 |
Correct |
5 ms |
376 KB |
Output is correct |
4 |
Correct |
5 ms |
504 KB |
Output is correct |
5 |
Correct |
5 ms |
376 KB |
Output is correct |
6 |
Correct |
5 ms |
380 KB |
Output is correct |
7 |
Correct |
5 ms |
376 KB |
Output is correct |
8 |
Correct |
5 ms |
376 KB |
Output is correct |
9 |
Correct |
5 ms |
376 KB |
Output is correct |
10 |
Correct |
5 ms |
408 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
6 ms |
376 KB |
Output is correct |
13 |
Correct |
5 ms |
376 KB |
Output is correct |
14 |
Correct |
5 ms |
376 KB |
Output is correct |
15 |
Correct |
5 ms |
376 KB |
Output is correct |
16 |
Correct |
5 ms |
376 KB |
Output is correct |
17 |
Correct |
5 ms |
376 KB |
Output is correct |
18 |
Correct |
5 ms |
376 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
5 ms |
504 KB |
Output is correct |
21 |
Correct |
5 ms |
376 KB |
Output is correct |
22 |
Correct |
5 ms |
376 KB |
Output is correct |
23 |
Correct |
5 ms |
376 KB |
Output is correct |
24 |
Correct |
5 ms |
376 KB |
Output is correct |
25 |
Correct |
5 ms |
376 KB |
Output is correct |
26 |
Correct |
6 ms |
376 KB |
Output is correct |
27 |
Correct |
5 ms |
376 KB |
Output is correct |
28 |
Correct |
5 ms |
376 KB |
Output is correct |
29 |
Correct |
5 ms |
376 KB |
Output is correct |
30 |
Correct |
5 ms |
504 KB |
Output is correct |
31 |
Correct |
5 ms |
380 KB |
Output is correct |
32 |
Correct |
5 ms |
376 KB |
Output is correct |
33 |
Correct |
5 ms |
376 KB |
Output is correct |
34 |
Correct |
5 ms |
376 KB |
Output is correct |
35 |
Correct |
5 ms |
380 KB |
Output is correct |
36 |
Correct |
5 ms |
376 KB |
Output is correct |
37 |
Correct |
5 ms |
376 KB |
Output is correct |
38 |
Correct |
80 ms |
2424 KB |
Output is correct |
39 |
Correct |
82 ms |
2552 KB |
Output is correct |
40 |
Correct |
35 ms |
2424 KB |
Output is correct |
41 |
Correct |
40 ms |
2420 KB |
Output is correct |
42 |
Correct |
18 ms |
2552 KB |
Output is correct |
43 |
Correct |
25 ms |
2412 KB |
Output is correct |
44 |
Correct |
65 ms |
2424 KB |
Output is correct |
45 |
Correct |
76 ms |
2552 KB |
Output is correct |
46 |
Correct |
85 ms |
2552 KB |
Output is correct |
47 |
Correct |
94 ms |
2424 KB |
Output is correct |
48 |
Correct |
78 ms |
2424 KB |
Output is correct |
49 |
Correct |
55 ms |
2680 KB |
Output is correct |
50 |
Correct |
56 ms |
2552 KB |
Output is correct |
51 |
Correct |
50 ms |
2552 KB |
Output is correct |
52 |
Correct |
44 ms |
2424 KB |
Output is correct |
53 |
Correct |
49 ms |
2552 KB |
Output is correct |
54 |
Correct |
26 ms |
2552 KB |
Output is correct |
55 |
Correct |
18 ms |
2424 KB |
Output is correct |
56 |
Correct |
17 ms |
2424 KB |
Output is correct |
57 |
Correct |
21 ms |
2424 KB |
Output is correct |
58 |
Correct |
18 ms |
2424 KB |
Output is correct |
59 |
Correct |
12 ms |
504 KB |
Output is correct |
60 |
Correct |
15 ms |
760 KB |
Output is correct |
61 |
Correct |
12 ms |
504 KB |
Output is correct |
62 |
Correct |
11 ms |
508 KB |
Output is correct |
63 |
Correct |
10 ms |
760 KB |
Output is correct |
64 |
Correct |
11 ms |
504 KB |
Output is correct |
65 |
Correct |
71 ms |
2424 KB |
Output is correct |
66 |
Correct |
62 ms |
2424 KB |
Output is correct |
67 |
Correct |
81 ms |
2680 KB |
Output is correct |
68 |
Correct |
55 ms |
2552 KB |
Output is correct |
69 |
Correct |
44 ms |
2424 KB |
Output is correct |
70 |
Correct |
48 ms |
2552 KB |
Output is correct |
71 |
Correct |
26 ms |
1144 KB |
Output is correct |
72 |
Correct |
12 ms |
1144 KB |
Output is correct |
73 |
Correct |
76 ms |
2424 KB |
Output is correct |
74 |
Correct |
8 ms |
2552 KB |
Output is correct |
75 |
Runtime error |
581 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
76 |
Halted |
0 ms |
0 KB |
- |