#include <bits/stdc++.h>
#include "aliens.h"
#ifdef MINA
#include "grader.cpp"
#endif
using namespace std;
#define ll long long
#define sz(x) (int) x.size()
const int N = 100'005;
const ll inf = 1e18;
array<ll, 2> dp[N];
ll take_photos(int n, int crap, int m, vector<int> R, vector<int> C) {
array<ll, 2> A[n + 1];
vector<ll> v;
for (int i = 1; i <= n; i++) {
A[i] = {R[i - 1], C[i - 1]};
if (A[i][0] > A[i][1]) swap(A[i][0], A[i][1]);
}
sort(A + 1, A + n + 1, [&] (array<ll, 2> x, array<ll, 2> y) {return make_pair(x[0], -x[1]) < make_pair(y[0], -y[1]);});
multiset<ll> s;
vector<array<ll, 2>> a = {{0, 0}};
for (int i = 1; i <= n; i++) {
while (s.size() && *s.begin() < A[i][0]) s.erase(s.begin());
if (s.size() && A[i][1] <= *s.rbegin()) continue;
a.push_back({A[i][0], A[i][1]});
s.insert(A[i][1]);
}
n = a.size() - 1;
ll prf[n + 2]{};
prf[1] = -1e18;
for (int i = 1; i <= n; i++) {
prf[i + 1] = max(prf[i], a[i][1]);
a[i][0]--;
prf[i] = max(prf[i], a[i][0]);
a[i][0] *= -2;
}
auto check = [&] (ll c) {
for (int i = 1; i <= n; i++) {
dp[i] = {inf, inf};
}
dp[0] = {0, 0};
auto cmp = [&] (int x, int y, int z) {
return (prf[y] * (prf[y] + a[y][0]) - prf[x] * (prf[x] + a[x][0]) - dp[y - 1][0] + dp[x - 1][0]) * (a[z][0] - a[y][0])
>= (prf[z] * (prf[z] + a[z][0]) - prf[y] * (prf[y] + a[y][0]) - dp[z - 1][0] + dp[y - 1][0]) * (a[y][0] - a[x][0]);
};
auto calc = [&] (int i, int k) {
return a[i][1] * a[k][0] - prf[k] * prf[k] - prf[k] * a[k][0] + dp[k - 1][0];
};
deque<int> dq;
int sz = 0;
for (int i = 1; i <= n; i++) {
while (sz - 2 >= 0 && cmp(dq[sz - 2], dq[sz - 1], i)) {
dq.pop_back();
sz--;
}
dq.push_back(i);
sz++;
while (1 < sz && calc(i, dq[1]) <= calc(i, dq[0])) {
dq.pop_front();
sz--;
}
dp[i][0] = calc(i, dq[0]) + a[i][1] * a[i][1] + c;
dp[i][1] = dp[dq[0] - 1][1] + 1;
}
return dp[n][1] <= m;
};
ll l = 0, r = 1e15;
while (l <= r) {
ll md = ((l + r) >> 1);
if (check(md)) {
r = md - 1;
} else {
l = md + 1;
}
}
ll k = l;
check(k);
return dp[n][0] - k * m;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
2 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
4 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 5 |
5 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 41 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 71923 |
7 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
8 |
Incorrect |
1 ms |
348 KB |
Wrong answer: output = 741, expected = 764 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 5 |
25 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 41 |
26 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
1 ms |
348 KB |
Wrong answer: output = 741, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 5 |
25 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 41 |
26 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
1 ms |
348 KB |
Wrong answer: output = 741, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 5 |
25 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 41 |
26 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
1 ms |
348 KB |
Wrong answer: output = 741, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 210 |
7 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 7696 |
9 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
10 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 2374 |
11 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 49 |
13 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 151 |
14 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 7220 |
16 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 7550 |
17 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 10000 |
19 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 10000 |
21 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
23 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 1 |
24 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 5 |
25 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 41 |
26 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
348 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
1 ms |
348 KB |
Wrong answer: output = 741, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |