Submission #440269

#	Time	Username	Problem	Language	Result	Execution time	Memory
440269		sebamarin	Aliens (IOI16_aliens)	C++14	25 / 100	2079 ms	78904 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],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

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