| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 440268 | sebamarin | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define COMPILE 1
// #define DEBUG 1
typedef long long ll;
typedef pair<ll,ll> ii;
#define db(x) cout<<#x<<" = "<<x<<"\n";
#define fore(i,a,b) for(ll i=a,ggdem=b;i<ggdem;i++)
#define FIN ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define SZ(a) ((ll)(a).size())
#define ALL(a) a.begin(),a.end()
#define mset(a,b) memset(a,b,sizeof(a));
#define pb push_back
#define fst first
#define snd second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// x,y -> -y,x
ll sq(ll x){return x*x;}
const ll N=4010,INF=1e18;
ll n,m,k,h,to[N],vis[N],qid,mat[N][N];
ii dp[N];
vector<ii>v;
ii solve(ll i) {
if(i==n)return {0ll,0ll};
if(vis[i]==qid)return dp[i];
vis[i]=qid;
ii res={INF,INF};
fore(k,i,n) {
ii a=solve(k+1);
ll bc=mat[i][k];
res=min(res,{a.fst+bc+h,a.snd+1});
// cout<<i<<" to "<<k<<" with "<<cost<<" "<<a.fst<<"+"<<b<<"-"<<c<<"+"<<h<<endl;
}
return dp[i]=res;
}
ii get_solve(ll alien) {
h=alien,qid++;
return solve(0);
}
ll take_photos(int _n,int _m,int _k,vector<int>r,vector<int> c) {
n=_n,m=_m,k=_k;
map<ll,ll>mp;
fore(i,0,n){
if(r[i]>c[i])swap(r[i],c[i]);
v.pb({r[i],c[i]});
ll pr=mp[r[i]];
mp[r[i]]=max(pr,1ll*c[i]);
}
sort(ALL(v));
v.pb({INF,INF});
ll y=0;
fore(i,0,n) {
y=max(y,mp[v[i].fst]);
to[i]=y;
}
#ifdef DEBUG
cout<<"v: "<<endl;for(auto it:v)cout<<it.fst<<" "<<it.snd<<endl;cout<<"n: "<<n<<endl;
cout<<"to: ";fore(i,0,n) cout<<to[i]<<" ";cout<<endl;
#endif
// fore(i,0,20) {
// cout<<i<<" : "<<get_solve(i).fst<<" "<<get_solve(i).snd<<endl;
// }
fore(i,0,n)fore(j,i,n)mat[i][j]=sq(to[j]-v[i].fst+1)-sq(max(0ll,to[j]-v[j+1].fst+1));
ll ml=0,mr=sq(m+1)+10ll;
while(ml<=mr) {
h=(ml+mr)/2,qid++;
if(solve(0).snd<=k)mr=h-1;
else ml=h+1;
}
#ifdef DEBUG
cout<<"done: "<<ml<<" "<<mr<<endl;
#endif
h=ml,qid++;
ii res=solve(0);
// cout<<ml<<" : "<<res.fst<<" "<<res.snd<<endl;
return res.fst-ml*k;
}
#ifdef COMPILE
int main() {FIN;
cin>>n>>m>>k;
vector<int>r(n),c(n);
fore(i,0,n)cin>>r[i]>>c[i];
cout<<take_photos(n,m,k,r,c)<<"\n";
}
#endif