| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 492254 | Killer2501 | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pll pair<ll, ll>
#define pb push_back
using namespace std;
const int N = 1e5+5;
const int M = 2e5+5;
const ll mod = 1e9+7;
const int base = 400;
const ll inf = 1e16;
ll ans, tong, n, k, a[N], b[N], m, c[N], d[N], t, lab[N], dp[N][2];
vector<pll> adj[N], kq;
string s;
pll p[N];
void cal(int l, int r, int opl, int opr, int j)
{
if(l > r)return;
int mid = (l+r)/2;
int best = mid;
dp[mid][j] = inf;
for(int i = opl; i <= min(mid, opr); i ++)
{
tong = dp[i-1][j^1] + (p[mid].se-p[i].fi+1)*(p[mid].se-p[i].fi+1);
if(i > 1)tong -= max(0ll, p[i-1].se-p[i].fi+1)*max(0ll, p[i-1].se-p[i].fi+1);
if(dp[mid][j] > tong)
{
dp[mid][j] = tong;
best = i;
}
}
cal(l, mid-1, opl, best, j);
cal(mid+1, r, best, opr, j);
}
bool cmp(pll& x, pll& y)
{
if(x.fi != y.fi)return x.fi < y.fi;
return x.se > y.se;
}
ll take_photos(int N, int M, int K, vector<int> r, vector<int> c)
{
n = N;
m = M;
k = K;
for(int i = 1; i <= n; i ++)
{
p[i].fi = r[i-1];
p[i].se = c[i-1];
if(p[i].fi > p[i].se)swap(p[i].fi, p[i].se);
}
sort(p+1, p+1+n, cmp);
for(int i = 1; i <= n; i ++)
{
if(!kq.empty() && kq.back().se >= p[i].se)continue;
kq.pb(p[i]);
}
n = kq.size();
for(int i = 1; i <= n; i ++)p[i] = kq[i-1];
for(int i = 1; i <= n; i ++)dp[i][0] = inf;
for(int j = 1; j <= k; j ++)
{
cal(1, n, 1, n, j&1);
}
return dp[n][k&1];
}
void sol()
{
vector<int> r, c;
cin >> n >> m >> k;
r.resize(n);
c.resize(n);
for(int i = 0; i < n; i ++)cin >> r[i];
for(int i = 0; i < n; i ++)cin >> c[i];
cout << take_photos(n, m, k, r, c);
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#define task "test"
if(fopen(task".inp", "r"))
{
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int ntest = 1;
//cin >> ntest;
while(ntest -- > 0)sol();
}
/*
9 2 1 9
5 1
*/