| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1046851 | Gromp15 | 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"
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
#define ar array
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ll long long
using namespace std;
template<typename T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const ll INF = 1e18;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<ar<int, 2>> a(n);
for (int i = 0; i < n; i++) {
a[i] = {r[i], c[i]};
if (r[i] > c[i]) swap(a[i][0], a[i][1]);
}
sort(all(a));
int mx = -1;
vector<ar<int, 2>> b;
for (int i = 0; i < n; i++) {
int r = i;
while (r+1 < n && a[r+1][0] == a[r][0]) r++;
if (a[r][1] > mx) {
b.push_back({a[r][0], a[r][1]});
mx = a[r][1];
}
i = r;
}
swap(a, b);
n = sz(a);
ll L = 0, R = 1e12, ans = -1;
while (L <= R) {
ll mid = (L+R)/2;
vector<ar<ll, 3>> dp(n+1, {INF, INF, -INF});
dp[0] = {0, 0, 0};
auto sq = [&](int x) { return (ll)x * x; };
deque<ar<ll, 4>> d;
auto f = [&](int j) {
return dp[j][0] + sq(a[j][0]) - 2 * a[j][0] - (j ? sq(max(0, a[j-1][1] - a[j][0] + 1)) : 0);
};
d.emplace_back({-2 * a[0][0], f(0), 0, 0});
auto query = [&](const ar<ll, 4>& x, int pos) {
return x[0] * pos + x[1];
};
auto inter = [&](const ar<ll, 4>& x1, const ar<ll, 4>& x2) {
return (double)(x2[1] - x1[1]) / (x1[0] - x2[0]);
};
for (int i = 1; i <= n; i++) {
ll C = sq(a[i-1][1]) + 2 * a[i-1][1] + 1 + mid;
int cur = a[i-1][1];
while (d.size() > 1 && query(d[1], cur) < query(d[0], cur)) d.pop_front();
dp[i][0] = query(d[0], cur) + C;
for (auto& x : d) {
if (query(x, cur) == query(d[0], cur)) {
ckmin(dp[i][1], x[2] + 1);
ckmax(dp[i][2], x[3] + 1);
}
else break;
}
if (i < n) {
ar<ll, 4> nw{-2 * a[i][0], f(i), dp[i][1], dp[i][2]};
while (d.size() > 1 && inter(d.end()[-2], nw) <= inter(d.end()[-2], d.end()[-1])) d.pop_back();
d.emplace_back(nw);
}
}
if (dp[n][1] <= k) {
int u = min(k, int(dp[n][2]));
ans = dp[n][0] - u * mid;
R = mid-1;
}
else L = mid+1;
}
return ans;
}