| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 440244 | sebamarin | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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=1024,INF=1e18;
ll n,m,k,dp[N][N],to[N];
vector<ii>v;
ll solve(ll i,ll j) {
if(j<0)return INF;
if(i==n)return 0ll;
if(dp[i][j]!=-1)return dp[i][j];
ll res=INF;
fore(k,i,n) {
ll a=solve(k+1,j-1);
ll b=sq(to[k]-v[i].fst+1);
ll c=sq(max(0ll,to[k]-v[k+1].fst+1));
ll cost=a+b-c;
res=min(res,cost);
// cout<<i<<" "<<j<<" to "<<k+1<<" "<<j-1<<" with "<<cost<<" "<<a<<"+"<<b<<"-"<<c<<endl;
}
return dp[i][j]=res;
}
ll take_photos(ll _n,ll _m,ll _k,vector<ll>r,vector<ll> 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,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
memset(dp,-1,sizeof(dp));
return solve(0,k);
}
#ifdef COMPILE
int main() {FIN;
cin>>n>>m>>k;
vector<ll>r(n),c(n);
fore(i,0,n)cin>>r[i]>>c[i];
cout<<take_photos(n,m,k,r,c)<<"\n";
}
#endif