| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 504174 | maximumSHOT | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ui = unsigned int;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
const int inf = 1e9;
const ll inf64 = 1e18;
struct output {
ll res;
void print() {
cout << res << "\n";
}
bool operator == (const output& o) const {
return res == o.res;
}
};
struct input {
int n, m, k;
vector<pii> a;
input() = default;
void read() {
cin >> n >> m >> k;
a.resize(n);
for (auto& [x, y] : a)
cin >> x >> y;
}
void print() {
cout << n << " " << m << " " << k << "\n";
for (auto [x, y] : a)
cout << x << " " << y << "\n";
}
void gen() {
static mt19937 rnd(42);
const int MAXN = 5;
n = rnd() % MAXN + 1;
m = rnd() % MAXN + 1;
k = rnd() % n + 1;
a.resize(n);
for (auto& [x, y] : a) {
x = rnd() % m;
y = rnd() % m;
}
}
void gen_max_test() {
}
void prepare() {
for (auto& [x, y] : a) {
if (y > x)
swap(x, y);
}
vector<pii> st;
for (int i = 0; i < n; i++) {
if (i > 0 && a[i].first == a[i - 1].first)
continue;
while (!st.empty() && st.back().second >= a[i].second)
st.pop_back();
st.push_back(a[i]);
}
a = st;
n = (int) a.size();
}
ll f(int len) {
return 1ll * len * len;
}
output fast() {
prepare();
vector<ll> rem(n);
for (int j = 0; j < n; j++)
rem[j] = f(max(0, (j > 0 ? a[j - 1].first : -1) - a[j].second + 1));
vector<vector<ll>> dp(n, vector<ll>(k + 1, inf64));
for (int i = 0; i < n; i++) {
for (int j = i; j >= 0; j--) {
ll cost = f(a[i].first - a[j].second + 1) - rem[j];
for (int c = 1; c <= k; c++)
dp[i][c] = min(dp[i][c], (j > 0 ? dp[j - 1][c - 1] : 0) + cost);
}
}
ll res = inf64;
for (int c = 1; c <= k; c++)
res = min(res, dp[n - 1][c]);
return output{res};
}
output slow() {
#ifndef DEBUG
throw;
#endif
prepare();
vector<vector<ll>> dp(n, vector<ll>(k + 1, inf64));
for (int i = 0; i < n; i++) {
for (int j = i; j >= 0; j--) {
ll cost =
f(a[i].first - a[j].second + 1) -
f(max(0, (j > 0 ? a[j - 1].first : -1) - a[j].second + 1));
for (int c = 1; c <= k; c++)
dp[i][c] = min(dp[i][c], (j > 0 ? dp[j - 1][c - 1] : 0) + cost);
}
}
ll res = inf64;
for (int c = 1; c <= k; c++)
res = min(res, dp[n - 1][c]);
return output{res};
}
};
void test_case() {
input in;
in.read();
output res = in.fast();
res.print();
}
void work() {
int t = 1;
while (t--)
test_case();
}
void test() {
for (int t = 1;;t++) {
input in;
in.gen();
input in_fs = in;
input in_sl = in;
output fs = in_fs.fast();
output sl = in_sl.slow();
if (fs == sl) {
cout << "OK" << endl;
fs.print();
cout << "\n=========" << endl;
} else {
cout << "WA " << t << "\n";
cout << "exp\n";
sl.print();
cout << "\n=========\n";
cout << "fnd\n";
fs.print();
cout << "\n=========\n";
in.print();
break;
}
}
}
void max_test() {
input in;
in.gen_max_test();
input in_fs = in;
output fs = in_fs.fast();
fs.print();
}
#ifdef DEBUG
int main() {
#ifdef DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(0);
cin.tie(0);
work();
// test();
// max_test();
return 0;
}
#else
ll take_photos(int n, int m, int k, int[] r, int[] c) {
input in;
in.n = n;
in.m = m;
in.k = k;
in.a.resize(n);
for (int i = 0; i < n; i++)
in.a[i] = {r[i], c[i]};
output fs = in.fast();
return fs.res;
}
#endif