Submission #440263

#	Time	Username	Problem	Language	Result	Execution time	Memory
440263		sebamarin	Aliens (IOI16_aliens)	C++14	25 / 100	2055 ms	1064 KiB

aliens

#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];
bool vis[N];
ii dp[N];
vector<ii>v;
ii solve(ll i) {
  if(i==n)return {0ll,0ll};
  if(vis[i])return dp[i];
  vis[i]=1;
  ii res={INF,INF};
  fore(k,i,n) {
    ii a=solve(k+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.fst+b-c+h;
    res=min(res,{cost,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;
  memset(vis,0,sizeof(vis));
  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;
  // }
  ll ml=0,mr=sq(m+1)+10ll;
  while(ml<=mr) {
    h=(ml+mr)/2;
    memset(vis,0,sizeof(vis));
    ii it=get_solve(h);
    if(it.snd<=k)mr=h-1;
    else ml=h+1;
  }
  #ifdef DEBUG
    cout<<"done: "<<ml<<" "<<mr<<endl;
  #endif
  ii res=get_solve(ml);
  // 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

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40