| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 330758 | IgorI | 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 <bits/stdc++.h>
using namespace std;
const long long INFLL = 1e18;
pair<long long, long long> calc(int n, long long M, vector<int> l, vector<int> r)
{
vector<long long> dp(n, INFLL);
vector<long long> bl(n, INFLL);
for (int i = 0; i < n; i++)
dp[i] = M + 1ll * (r[i] - l[0] + 1) * (r[i] - l[0] + 1), bl[i] = 1;
struct line{
long long k, b, id;
};
vector<line> convex;
int lj = 0;
for (int i = 0; i < n; i++)
{
long long res = 1ll * r[i] * r[i];
long long d = INFLL, used = 0;
for (int j = 0; j < convex.size(); j++)
{
line e = convex[j];
if (e.b + e.k * r[i] < d)
{
d = e.b + e.k * r[i], used = INFLL;
lj = j;
}
if (e.b + e.k * r[i] == d && bl[e.id] < used)
{
used = bl[e.id];
lj = j;
}
if (j > lj + 1)
break;
}
res += d;
if (res < dp[i])
dp[i] = res, bl[i] = used + 1;
if (i + 1 < n)
{
long long b = dp[i] + 1ll * l[i + 1] * l[i + 1] + 1 - 2 * l[i + 1] + M - 1ll * max(0, r[i] - l[i + 1] + 1) * max(0, r[i] - l[i + 1] + 1);
long long k = 2 * (1 - l[i + 1]);
line L = {k, b, i};
while (convex.size() >= 2)
{
line A = convex[convex.size() - 2];
line B = convex[convex.size() - 1];
if (1ll * (B.b - L.b) * (L.k - B.k) > 1ll * (A.b - L.b) * (L.k - B.k))
convex.pop_back();
else
break;
}
convex.push_back(L);
}
}
//cout << M << " " << dp[n - 1] << " " << bl[n - 1] << endl;
return {dp[n - 1], bl[n - 1]};
}
long long take_photos(int n, int m, int k, vector<int> l, vector<int> r)
{
vector<int> cv(m);
for (int i = 0; i < m; i++)
{
cv[i] = i + 1;
}
for (int i = 0; i < n; i++)
{
int x = min(l[i], r[i]);
int y = max(l[i], r[i]);
cv[y] = min(cv[y], x);
}
l.clear();
r.clear();
for (int i = 0; i < m; i++)
{
if (cv[i] <= i)
{
while (l.size() && l.back() >= cv[i])
l.pop_back(), r.pop_back();
l.push_back(cv[i]), r.push_back(i);
}
}
n = l.size();
//for (int i = 0; i < l.size(); i++)
// cout << l[i] << " " << r[i] << endl;
long long L = 0, R = 1ll * m * m + 222;
long long ans = INFLL;
k = min(k, n);
while (L + 1 < R)
{
long long M = (L + R) / 2;
if (calc(n, M, l, r).second >= k)
L = M;
else
R = M;
}
for (long long d = R - 1; d <= R; d++)
{
pair<long long, long long> res = calc(n, d, l, r);
//cout << res.first << " " << res.second << " " << d << " " << k << endl;
if (res.second <= k)
ans = min(ans, res.first - 1ll * k * d);
}
return ans;
}
void solve(int g, vector<int> &l, vector<int> &r, vector<vector<long long> > &dp, int le_i, int ri_i, int le_p, int ri_p)
{
if (le_i > ri_i) return;
int mid_i = (le_i + ri_i) / 2;
int id = le_p;
for (int p = le_p; p <= ri_p && p < mid_i; p++)
{
long long res = dp[p][g - 1];
long long L = l[p], R = r[mid_i - 1], covto = -1;
if (p) covto = r[p - 1];
if (covto < L)
res += 1ll * (R - L + 1) * (R - L + 1);
else
res += 1ll * (R - L + 1) * (R - L + 1) - 1ll * (covto - L + 1) * (covto - L + 1);
if (res < dp[mid_i][g])
{
id = p;
dp[mid_i][g] = res;
}
}
solve(g, l, r, dp, le_i, mid_i - 1, le_p, id);
solve(g, l, r, dp, mid_i + 1, ri_i, id, ri_p);
}
long long take_photos2(int n, int m, int k, vector<int> l, vector<int> r)
{
vector<int> cv(m);
for (int i = 0; i < m; i++)
{
cv[i] = i + 1;
}
for (int i = 0; i < n; i++)
{
int x = min(l[i], r[i]);
int y = max(l[i], r[i]);
cv[y] = min(cv[y], x);
}
l.clear();
r.clear();
for (int i = 0; i < m; i++)
{
if (cv[i] <= i)
{
while (l.size() && l.back() >= cv[i])
l.pop_back(), r.pop_back();
l.push_back(cv[i]), r.push_back(i);
}
}
n = l.size();
const long long INFLL = 1e18;
vector<vector<long long> > dp(n + 1, vector<long long>(k + 1, INFLL));
dp[0][0] = 0;
for (int g = 1; g <= k; g++)
{
solve(g, l, r, dp, 1, n, 0, n);
}
return *min_element(dp[n].begin(), dp[n].end());
}
signed main()
{
freopen("80", "r", stdin);
srand(time(NULL));
int n, m, k;
cin >> n >> m >> k;
while (1)
{
vector<int> r(n), c(n);
for (int i = 0; i < n; i++)
{
//r[i] = rand() % m;
//c[i] = rand() % m;
//cout << r[i] << " " << c[i] << endl;
cin >> r[i] >> c[i];
}
long long a = take_photos(n, m, k, r, c);
long long b = take_photos2(n, m, k, r, c);
cout << a << endl << b << endl << endl;
//if (a != b)
return 0;
}
}