# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
370148 |
2021-02-23T12:11:54 Z |
KoD |
Aliens (IOI16_aliens) |
C++17 |
|
1 ms |
384 KB |
#include <bits/stdc++.h>
#include "aliens.h"
template <class T>
using Vec = std::vector<T>;
using ll = long long;
using bigll = __int128_t;
constexpr ll square(const ll x) {
return x * x;
}
struct Line {
ll a, b;
ll get(const ll x) const {
return a * x + b;
}
};
struct CHT {
std::deque<Line> line;
CHT(): line() { }
void add(const Line &l) {
while (line.size() >= 2) {
const auto &m = line[line.size() - 1];
const auto &n = line[line.size() - 2];
if (bigll(m.b - n.b) * bigll(m.a - l.a) < bigll(l.b - m.b) * bigll(n.a - m.a)) {
break;
}
line.pop_back();
}
line.push_back(l);
}
ll get(const ll x) {
while (line.size() >= 2) {
const auto &m = line[0];
const auto &n = line[1];
if (m.get(x) < n.get(x)) {
break;
}
line.pop_front();
}
return line[0].get(x);
}
};
ll take_photos(int n, int m, int k, Vec<int> r, Vec<int> c) {
Vec<std::pair<int, int>> star;
{
for (int i = 0; i < n; ++i) {
if (r[i] > c[i]) {
std::swap(r[i], c[i]);
}
c[i] += 1;
}
Vec<int> order(n);
std::iota(order.begin(), order.end(), (int) 0);
std::sort(order.begin(), order.end(), [&](const int i, const int j) {
if (r[i] == r[j]) return c[i] > c[j];
return r[i] < r[j];
});
int last_c = -1;
for (const int i: order) {
if (last_c < c[i]) {
star.emplace_back(r[i], c[i]);
last_c = c[i];
}
}
}
n = (int) star.size();
const ll fix_coeff = n + 1;
const auto compute = [&](const ll penalty) {
Vec<ll> dp(n + 1);
CHT cht;
for (int i = 0; i < n; ++i) {
const ll a = fix_coeff * (-2 * star[i].first);
const ll dup = (i == 0 ? 0 : std::max(star[i - 1].second - star[i].first, 0));
const ll b = dp[i] + fix_coeff * (square(star[i].first) - square(dup));
cht.add(Line { a, b });
dp[i + 1] = cht.get(star[i].second) + fix_coeff * (square(star[i].second) + penalty) + 1;
}
return std::make_pair(dp[n] / fix_coeff, dp[n] % fix_coeff);
};
ll ng = -1, ok = (ll) m * m + 1;
while (ok - ng > 1) {
const ll md = (ok + ng) / 2;
(compute(md).second <= k ? ok : ng) = md;
}
const auto [cost, usage] = compute(ok);
return (cost - ok * usage) + ok * (k - usage);
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
256 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 10000 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Correct answer: answer = 1 |
2 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 1 |
4 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 5 |
5 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 41 |
6 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 71923 |
7 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 77137 |
8 |
Incorrect |
1 ms |
364 KB |
Wrong answer: output = 1086, expected = 764 |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
256 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
384 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 1 |
24 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 5 |
25 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 41 |
26 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
1 ms |
364 KB |
Wrong answer: output = 1086, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
256 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
384 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 1 |
24 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 5 |
25 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 41 |
26 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
1 ms |
364 KB |
Wrong answer: output = 1086, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
256 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
384 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 1 |
24 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 5 |
25 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 41 |
26 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
1 ms |
364 KB |
Wrong answer: output = 1086, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
2 |
Correct |
1 ms |
256 KB |
Correct answer: answer = 4 |
3 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 4 |
4 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 12 |
5 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 52 |
6 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 210 |
7 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 88 |
8 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 7696 |
9 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 1 |
10 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 2374 |
11 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 9502 |
12 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 49 |
13 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 151 |
14 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7550 |
15 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7220 |
16 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 7550 |
17 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 10000 |
18 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 10000 |
19 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 624 |
20 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 10000 |
21 |
Correct |
1 ms |
384 KB |
Correct answer: answer = 1 |
22 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 4 |
23 |
Correct |
0 ms |
364 KB |
Correct answer: answer = 1 |
24 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 5 |
25 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 41 |
26 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 71923 |
27 |
Correct |
1 ms |
364 KB |
Correct answer: answer = 77137 |
28 |
Incorrect |
1 ms |
364 KB |
Wrong answer: output = 1086, expected = 764 |
29 |
Halted |
0 ms |
0 KB |
- |