# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
393305 |
2021-04-23T07:22:57 Z |
Tc14 |
Aliens (IOI16_aliens) |
C++17 |
|
1 ms |
208 KB |
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;
const ll LLINF = (ll)1e18 + 10;
ve<pii> P;
ve<ll> L;
int a;
struct segment {
ll m, b, l, r, k;
};
double intersect(ll m1, ll m2, ll b1, ll b2) {
return (double) (b1 - b2) / (double) (m2 - m1);
}
ll sq(int x) { return (ll)x*x; }
pair<ll, ll> calc(ll lambda) {
ve<ll> DP(a), T(a);
list<segment> H;
DP[0] = sq(P[0].second - P[0].first + 1) - lambda;
T[0] = 1;
for (int i = 1; i < a; i++) {
ll x = -P[i].first + 1;
ll b = DP[i - 1] - L[i] + x * x;
ll m = 2 * x;
if (H.size() == 0) H.push_back({m, b, -LLINF, LLINF, T[i - 1]});
else {
while (intersect(H.back().m, m, H.back().b, b) < (double)H.back().l) {
H.pop_back();
}
double z = intersect(H.back().m, m, H.back().b, b);
if ((H.back().b - b) % (m - H.back().m) == 0) {
if ((H.back().b - b) / (m - H.back().m) == (double)H.back().l) {
assert(false);
}
}
ll l = (ll)ceil(z);
H.back().r = (ll)floor(z);
H.push_back({m, b, l, LLINF, T[i - 1]});
}
while (H.begin()->r < P[i].second) {
H.pop_front();
}
H.begin()->l = -LLINF;
ll q = H.begin()->m * P[i].second + H.begin()->b;
ll v = q + sq(P[i].second) - lambda;
DP[i] = sq(P[i].second - P[0].first + 1) - lambda;
T[i] = 1;
if (DP[i] > v) {
DP[i] = v;
T[i] = H.begin()->k + 1;
}
}
return {DP[a - 1], T[a - 1]};
}
ll take_photos(int n, int m, int k, ve<int> R, ve<int> C) {
map<int, int> M;
for (int i = 0; i < n; i++) {
int r = R[i];
int c = C[i];
if (c < r) swap(r, c);
if (M.find(r) == M.end()) M[r] = c;
else M[r] = max(M[r], c);
}
int cOld = -1;
a = 0;
for (pii p : M) {
int r, c;
tie(r, c) = p;
if (c > cOld) {
cOld = c;
P.push_back({r, c});
a++;
}
}
L = ve<ll>(a);
for (int i = 1; i < a; i++) {
if (P[i - 1].second >= P[i].first) {
L[i] = sq(P[i - 1].second - P[i].first + 1);
}
}
ll lo = 0;
ll hi = (ll)1e9;
ll v, t;
ll mid = (lo + hi) / 2;
while (lo < hi) {
mid = (lo + hi) / 2;
tie(v, t) = calc(mid);
if (t > min(a, k)) lo = mid + 1;
else if (t <= min(a, k)) hi = mid;
}
return v + min(a, k) * mid;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
208 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 1 |
2 |
Incorrect |
1 ms |
204 KB |
Wrong answer: output = -999999997, expected = 4 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
208 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 1 |
22 |
Incorrect |
1 ms |
204 KB |
Wrong answer: output = -999999997, expected = 4 |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
208 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 1 |
22 |
Incorrect |
1 ms |
204 KB |
Wrong answer: output = -999999997, expected = 4 |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
208 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 1 |
22 |
Incorrect |
1 ms |
204 KB |
Wrong answer: output = -999999997, expected = 4 |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 4 |
4 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 12 |
5 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 52 |
6 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 88 |
8 |
Correct |
1 ms |
208 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 624 |
20 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
204 KB |
Correct answer: answer = 1 |
22 |
Incorrect |
1 ms |
204 KB |
Wrong answer: output = -999999997, expected = 4 |
23 |
Halted |
0 ms |
0 KB |
- |