| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 682633 | krzsal | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
#ifdef LOCAL
ostream &operator<<(ostream &out, string str)
{
for (char c : str)
out << c;
return out;
}
template <class L, class R>
ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.first << ", " << p.second << ")"; }
template <class L, class R, class S>
ostream &operator<<(ostream &out, tuple<L, R, S> p)
{
auto &[a, b, c] = p;
return out << "(" << a << ", " << b << ", " << c << ")";
}
template <class T>
auto operator<<(ostream &out, T a) -> decltype(a.begin(), out)
{
out << '{';
for (auto it = a.begin(); it != a.end(); it = next(it))
out << (it != a.begin() ? ", " : "") << *it;
return out << '}';
}
void dump() { cerr << "\n"; }
template <class T, class... Ts>
void dump(T a, Ts... x)
{
cerr << a << ", ";
dump(x...);
}
#define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#define debug(...) 42
#endif
struct ev
{
ll cost, num, last, size;
};
ll take_photos(int m, int n, int k, int *r, int *c)
{
vl V(n);
for (int i = 0; i < n; i++)
V[i] = i;
for (int i = 0; i < m; i++)
V[min(r[i], c[i])] = max(V[min(r[i], c[i])], ll(max(r[i], c[i])) + 1);
int st = 0;
while (st < n && V[st] == st)
st++;
if (st == n)
return 0;
// debug(st, V);
ll a = 0, b = ll(n) * ll(n);
ll ans;
while (a < b)
{
ll s = (a + b) / 2;
vector<ev> DP(n);
DP[st] = ev{V[st] * V[st] + s, 1, 0, V[st]};
for (int i = st + 1; i < n; i++)
{
ll oldCost = DP[i - 1].cost, newCost = DP[i - 1].cost + (V[i] - i) * (V[i] - i) + s;
if (V[i] > DP[i - 1].size)
{
oldCost += (V[i] - DP[i - 1].last) * (V[i] - DP[i - 1].last);
oldCost -= (DP[i - 1].size - DP[i - 1].last) * (DP[i - 1].size - DP[i - 1].last);
}
if (DP[i - 1].size > i)
newCost -= (DP[i - 1].size - i) * (DP[i - 1].size - i);
if (V[i] > DP[i - 1].size && newCost < oldCost)
DP[i] = ev{newCost, DP[i - 1].num + 1, i, V[i]};
else
{
DP[i] = DP[i - 1];
DP[i].cost = oldCost;
}
}
ans = DP.back().cost - DP.back().num * s;
if (DP.back().num > k)
a = s + 1;
else
b = s;
}
return ans;
}