#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using pli = pair<long long, int>;
#define ff first
#define ss second
int N, M;
vector<pii> P, xx;
const int SIZE = 1 << 11;
struct ST {
pli A[2 * SIZE];
void update(int x, pli v) {
x += SIZE; A[x] = v;
for (x >>= 1; x; x >>= 1) {
A[x].ff = A[x << 1].ff + A[x << 1 | 1].ff;
A[x].ss = A[x << 1].ss + A[x << 1 | 1].ss;
}
}
long long query(int v) {
int x = 1;
long long ret = 0;
while (x < SIZE) {
if (A[x << 1 | 1].ss >= v) x = x << 1 | 1;
else {
x <<= 1;
ret += A[x | 1].ff;
v -= A[x | 1].ss;
}
}
return ret + A[x].ff;
}
} seg;
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> N >> M;
if (N > 2000) assert(0);
for (int i = 0; i < N; ++i) {
int x, y; cin >> y >> x;
P.emplace_back(x, y);
}
sort(P.begin(), P.end());
for (int i = 0; i < N; ++i) xx.emplace_back(P[i].ss, i);
sort(xx.begin(), xx.end());
for (int i = 0; i < N; ++i) P[i].ss = lower_bound(xx.begin(), xx.end(), pii(P[i].ss, i)) - xx.begin();
long long ans = -1e18;
for (int i = 0; i < P.size(); ++i) {
for (int j = i; j < P.size(); ++j) {
seg.update(P[j].ss, pii(xx[P[j].ss].ff, 1));
if (j - i + 1 >= M) ans = max(ans, seg.query(M) - 2 * (P[j].ff - P[i].ff));
}
memset(seg.A, 0, sizeof(seg.A));
}
cout << ans;
return 0;
}
Compilation message
cake3.cpp: In function 'int main()':
cake3.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < P.size(); ++i) {
~~^~~~~~~~~~
cake3.cpp:49:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = i; j < P.size(); ++j) {
~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
11 |
Correct |
3 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
3 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
380 KB |
Output is correct |
15 |
Correct |
3 ms |
376 KB |
Output is correct |
16 |
Correct |
3 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
376 KB |
Output is correct |
18 |
Correct |
3 ms |
376 KB |
Output is correct |
19 |
Correct |
3 ms |
380 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
3 ms |
376 KB |
Output is correct |
25 |
Correct |
3 ms |
376 KB |
Output is correct |
26 |
Correct |
3 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
380 KB |
Output is correct |
28 |
Correct |
3 ms |
376 KB |
Output is correct |
29 |
Correct |
3 ms |
376 KB |
Output is correct |
30 |
Correct |
3 ms |
376 KB |
Output is correct |
31 |
Correct |
3 ms |
376 KB |
Output is correct |
32 |
Correct |
9 ms |
376 KB |
Output is correct |
33 |
Correct |
3 ms |
376 KB |
Output is correct |
34 |
Correct |
3 ms |
376 KB |
Output is correct |
35 |
Correct |
3 ms |
504 KB |
Output is correct |
36 |
Correct |
3 ms |
376 KB |
Output is correct |
37 |
Correct |
3 ms |
380 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
11 |
Correct |
3 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
3 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
380 KB |
Output is correct |
15 |
Correct |
3 ms |
376 KB |
Output is correct |
16 |
Correct |
3 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
376 KB |
Output is correct |
18 |
Correct |
3 ms |
376 KB |
Output is correct |
19 |
Correct |
3 ms |
380 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
3 ms |
376 KB |
Output is correct |
25 |
Correct |
3 ms |
376 KB |
Output is correct |
26 |
Correct |
3 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
380 KB |
Output is correct |
28 |
Correct |
3 ms |
376 KB |
Output is correct |
29 |
Correct |
3 ms |
376 KB |
Output is correct |
30 |
Correct |
3 ms |
376 KB |
Output is correct |
31 |
Correct |
3 ms |
376 KB |
Output is correct |
32 |
Correct |
9 ms |
376 KB |
Output is correct |
33 |
Correct |
3 ms |
376 KB |
Output is correct |
34 |
Correct |
3 ms |
376 KB |
Output is correct |
35 |
Correct |
3 ms |
504 KB |
Output is correct |
36 |
Correct |
3 ms |
376 KB |
Output is correct |
37 |
Correct |
3 ms |
380 KB |
Output is correct |
38 |
Correct |
97 ms |
604 KB |
Output is correct |
39 |
Correct |
103 ms |
504 KB |
Output is correct |
40 |
Correct |
74 ms |
504 KB |
Output is correct |
41 |
Correct |
76 ms |
504 KB |
Output is correct |
42 |
Correct |
65 ms |
504 KB |
Output is correct |
43 |
Correct |
63 ms |
504 KB |
Output is correct |
44 |
Correct |
87 ms |
504 KB |
Output is correct |
45 |
Correct |
100 ms |
504 KB |
Output is correct |
46 |
Correct |
108 ms |
504 KB |
Output is correct |
47 |
Correct |
106 ms |
504 KB |
Output is correct |
48 |
Correct |
95 ms |
504 KB |
Output is correct |
49 |
Correct |
89 ms |
632 KB |
Output is correct |
50 |
Correct |
90 ms |
528 KB |
Output is correct |
51 |
Correct |
86 ms |
524 KB |
Output is correct |
52 |
Correct |
79 ms |
524 KB |
Output is correct |
53 |
Correct |
83 ms |
508 KB |
Output is correct |
54 |
Correct |
72 ms |
504 KB |
Output is correct |
55 |
Correct |
64 ms |
504 KB |
Output is correct |
56 |
Correct |
63 ms |
632 KB |
Output is correct |
57 |
Correct |
75 ms |
632 KB |
Output is correct |
58 |
Correct |
65 ms |
504 KB |
Output is correct |
59 |
Correct |
86 ms |
504 KB |
Output is correct |
60 |
Correct |
100 ms |
524 KB |
Output is correct |
61 |
Correct |
94 ms |
504 KB |
Output is correct |
62 |
Correct |
81 ms |
632 KB |
Output is correct |
63 |
Correct |
87 ms |
504 KB |
Output is correct |
64 |
Correct |
86 ms |
504 KB |
Output is correct |
65 |
Correct |
91 ms |
556 KB |
Output is correct |
66 |
Correct |
86 ms |
504 KB |
Output is correct |
67 |
Correct |
100 ms |
504 KB |
Output is correct |
68 |
Correct |
89 ms |
524 KB |
Output is correct |
69 |
Correct |
84 ms |
504 KB |
Output is correct |
70 |
Correct |
81 ms |
504 KB |
Output is correct |
71 |
Correct |
110 ms |
504 KB |
Output is correct |
72 |
Correct |
78 ms |
516 KB |
Output is correct |
73 |
Correct |
105 ms |
520 KB |
Output is correct |
74 |
Correct |
65 ms |
632 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
3 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
3 ms |
376 KB |
Output is correct |
6 |
Correct |
3 ms |
376 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
3 ms |
376 KB |
Output is correct |
10 |
Correct |
3 ms |
376 KB |
Output is correct |
11 |
Correct |
3 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
3 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
380 KB |
Output is correct |
15 |
Correct |
3 ms |
376 KB |
Output is correct |
16 |
Correct |
3 ms |
376 KB |
Output is correct |
17 |
Correct |
3 ms |
376 KB |
Output is correct |
18 |
Correct |
3 ms |
376 KB |
Output is correct |
19 |
Correct |
3 ms |
380 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
3 ms |
376 KB |
Output is correct |
25 |
Correct |
3 ms |
376 KB |
Output is correct |
26 |
Correct |
3 ms |
376 KB |
Output is correct |
27 |
Correct |
3 ms |
380 KB |
Output is correct |
28 |
Correct |
3 ms |
376 KB |
Output is correct |
29 |
Correct |
3 ms |
376 KB |
Output is correct |
30 |
Correct |
3 ms |
376 KB |
Output is correct |
31 |
Correct |
3 ms |
376 KB |
Output is correct |
32 |
Correct |
9 ms |
376 KB |
Output is correct |
33 |
Correct |
3 ms |
376 KB |
Output is correct |
34 |
Correct |
3 ms |
376 KB |
Output is correct |
35 |
Correct |
3 ms |
504 KB |
Output is correct |
36 |
Correct |
3 ms |
376 KB |
Output is correct |
37 |
Correct |
3 ms |
380 KB |
Output is correct |
38 |
Correct |
97 ms |
604 KB |
Output is correct |
39 |
Correct |
103 ms |
504 KB |
Output is correct |
40 |
Correct |
74 ms |
504 KB |
Output is correct |
41 |
Correct |
76 ms |
504 KB |
Output is correct |
42 |
Correct |
65 ms |
504 KB |
Output is correct |
43 |
Correct |
63 ms |
504 KB |
Output is correct |
44 |
Correct |
87 ms |
504 KB |
Output is correct |
45 |
Correct |
100 ms |
504 KB |
Output is correct |
46 |
Correct |
108 ms |
504 KB |
Output is correct |
47 |
Correct |
106 ms |
504 KB |
Output is correct |
48 |
Correct |
95 ms |
504 KB |
Output is correct |
49 |
Correct |
89 ms |
632 KB |
Output is correct |
50 |
Correct |
90 ms |
528 KB |
Output is correct |
51 |
Correct |
86 ms |
524 KB |
Output is correct |
52 |
Correct |
79 ms |
524 KB |
Output is correct |
53 |
Correct |
83 ms |
508 KB |
Output is correct |
54 |
Correct |
72 ms |
504 KB |
Output is correct |
55 |
Correct |
64 ms |
504 KB |
Output is correct |
56 |
Correct |
63 ms |
632 KB |
Output is correct |
57 |
Correct |
75 ms |
632 KB |
Output is correct |
58 |
Correct |
65 ms |
504 KB |
Output is correct |
59 |
Correct |
86 ms |
504 KB |
Output is correct |
60 |
Correct |
100 ms |
524 KB |
Output is correct |
61 |
Correct |
94 ms |
504 KB |
Output is correct |
62 |
Correct |
81 ms |
632 KB |
Output is correct |
63 |
Correct |
87 ms |
504 KB |
Output is correct |
64 |
Correct |
86 ms |
504 KB |
Output is correct |
65 |
Correct |
91 ms |
556 KB |
Output is correct |
66 |
Correct |
86 ms |
504 KB |
Output is correct |
67 |
Correct |
100 ms |
504 KB |
Output is correct |
68 |
Correct |
89 ms |
524 KB |
Output is correct |
69 |
Correct |
84 ms |
504 KB |
Output is correct |
70 |
Correct |
81 ms |
504 KB |
Output is correct |
71 |
Correct |
110 ms |
504 KB |
Output is correct |
72 |
Correct |
78 ms |
516 KB |
Output is correct |
73 |
Correct |
105 ms |
520 KB |
Output is correct |
74 |
Correct |
65 ms |
632 KB |
Output is correct |
75 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
76 |
Halted |
0 ms |
0 KB |
- |