제출 #440245

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
440245		sebamarin	Aliens (IOI16_aliens)	C++14	25 / 100	178 ms	17768 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=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(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
  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

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