| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 700985 | rembocoder | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
bool cmp(const pair<int64_t, int64_t>& a, const pair<int64_t, int64_t>& b) {
if (a.first != b.first) {
return a.first < b.first;
}
return a.second > b.second;
}
int64_t divide_up(int64_t a, int64_t b) {
if (b < 0) {
a = -a;
b = -b;
}
if (a >= 0) {
return (a + b - 1) / b;
}
return a / b;
}
long long take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> points_x, vector<int32_t> points_y) {
vector<pair<int64_t, int64_t>> segs(n);
for (int64_t i = 0; i < n; i++) {
segs[i] = {min(points_x[i], points_y[i]), max(points_x[i], points_y[i])};
}
sort(segs.begin(), segs.end(), cmp);
vector<pair<int64_t, int64_t>> new_segs;
new_segs.push_back({-1, -1});
int64_t largest_r = -2e18;
for (auto [l, r]: segs) {
if (r <= largest_r) {
continue;
}
largest_r = r;
new_segs.push_back({l, r});
}
segs = new_segs;
n = segs.size();
new_segs.clear();
vector<vector<int64_t>> a(k + 1, vector<int64_t>(n));
vector<int64_t> b(n);
for (int64_t i = 0; i < n - 1; i++) {
b[i] = -2 * segs[i + 1].first;
}
vector<vector<int64_t>> dp(k + 1, vector<int64_t>(n, 2e18));
auto count_a = [&](int64_t j, int64_t i) {
if (i == n - 1) {
return;
}
a[j][i] = dp[j][i] + (segs[i + 1].first - 1) * (segs[i + 1].first - 1)
- max(0ll, segs[i].second - segs[i + 1].first + 1) *
max(0ll, segs[i].second - segs[i + 1].first + 1);
};
vector<vector<pair<int64_t, int64_t>>> ch(k + 1);
vector<int64_t> last(k + 1);
dp[0][0] = 0;
count_a(0, 0);
ch[0].push_back({-1, 0});
for (int64_t i = 1; i < n; i++) {
for (int64_t j = 1; j <= i && j <= k; j++) {
// dp[j][i]
int64_t x = segs[i].second;
while (last[j - 1] + 1 < ch[j - 1].size() && ch[j - 1][last[j - 1] + 1].first <= x) {
last[j - 1]++;
}
int64_t from = ch[j - 1][last[j - 1]].second;
dp[j][i] = segs[i].second * segs[i].second + 2 * segs[i].second + a[j - 1][from] + b[from] * x;
//cerr << x << ' ' << from << endl;
//cerr << segs[i].second * segs[i].second - 2 * segs[i].second << ' ' << a[j - 1][from] << ' ' << << endl;
count_a(j, i);
if (i == n - 1) {
continue;
}
if (ch[j].empty()) {
ch[j].push_back({-1, i});
continue;
}
while (true) {
x = ch[j].back().first;
int64_t ind = ch[j].back().second;
if (a[j][ind] + b[ind] * x < a[j][i] + b[i] * x) {
break;
}
ch[j].pop_back();
}
int64_t ind = ch[j].back().second;
x = divide_up(a[j][i] - a[j][ind], b[ind] - b[i]);
ch[j].push_back({x, i});
last[j] = min(last[j], int64_t(ch[j].size() - 1));
}
}
int64_t ans = 2e18;
for (int64_t j = 1; j <= k; j++) {
ans = min(ans, dp[j][n - 1]);
}
return ans;
}