| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 786195 | phoebe | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define pii pair<int, int>
#define F first
#define S second
#define PB push_back
#define ALL(x) x.begin(), x.end()
#define FOR(i, n) for (int i = 0; i < n; i++)
#define NYOOM ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
const int INF = 1e9 + 7;
const ll LLINF = 1ll<<60;
const int maxn = 5e4 + 10;
int n, m, k, min_row[maxn * 4], max_col[maxn * 4];
pii points[maxn];
vector<int> dp_before(maxn), dp_cur(maxn);
void update_row(int x, int v, int tl = 0, int tr = maxn, int i = 1){
if (tl > x || tr < x) return;
if (tl == tr){
min_row[i] = v; return;
}
int tm = (tl + tr) / 2;
update_row(x, v, tl, tm, i * 2); update_row(x, v, tm + 1, tr, i * 2 + 1);
min_row[i] = min(min_row[i * 2], min_row[i * 2 + 1]);
}
void update_col(int x, int v, int tl = 0, int tr = maxn, int i = 1){
if (tl > x || tr < x) return;
if (tl == tr){
max_col[i] = v; return;
}
int tm = (tl + tr) / 2;
update_col(x, v, tl, tm, i * 2); update_col(x, v, tm + 1, tr, i * 2 + 1);
max_col[i] = max(max_col[i * 2], max_col[i * 2 + 1]);
}
int range_row(int l, int r, int tl = 0, int tr = maxn, int i = 1){
if (l > tr || tl > r) return LLINF;
if (l <= tl && tr <= r) return min_row[i];
int tm = (tl + tr) / 2;
return min(range_row(l, r, tl, tm, i * 2),
range_row(l, r, tm + 1, tr, i * 2 + 1));
}
int range_col(int l, int r, int tl = 0, int tr = maxn, int i = 1){
if (l > tr || tl > r) return -1;
if (l <= tl && tr <= r) return max_col[i];
int tm = (tl + tr) / 2;
return max(range_col(l, r, tl, tm, i * 2),
range_col(l, r, tm + 1, tr, i * 2 + 1));
}
int cost(int l, int r){ // [l, r]
int row = range_row(l, r), col = range_col(l, r);
return (col - row + 1) * (col - row + 1);
}
void solve(int l, int r, int optl, int optr){
if (l > r) return;
int mid = (l + r) / 2;
dp_cur[mid] = LLINF; int opt = -1;
for (int k = optl; k <= min(mid, optr); k++){
int v = cost(k, mid);
if (k != 0) v += dp_before[k - 1];
if (v < dp_cur[mid]) dp_cur[mid] = v, opt = k;
}
solve(l, mid - 1, optl, opt);
solve(mid + 1, r, opt, optr);
}
signed main(){
NYOOM;
fill(min_row, min_row + maxn * 4, INF);
fill(max_col, max_col + maxn * 4, -1);
cin >> n >> m >> k;
FOR(i, n){
cin >> points[i].F >> points[i].S;
if (points[i].S < points[i].F) swap(points[i].F, points[i].S);
}
sort(points, points + n);
FOR(i, n){
int r = points[i].F, c = points[i].S;
update_row(i, r); update_col(i, c);
}
FOR(i, n) dp_before[i] = cost(0, i);
for (int i = 2; i <= k; i++){
solve(0, n - 1, 0, n - 1);
dp_before = dp_cur;
}
cout << dp_before[n - 1];
}