Submission #1118962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118962		epicci23	Aliens (IOI16_aliens)	C++17	12 / 100	7 ms	516 KiB

aliens

#include "bits/stdc++.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;

const ll INF = 1e18;

vector<ll> dp,ndp;
vector<array<ll,2>> v;

void f(ll l,ll r,ll optl,ll optr){
  if(l>r) return;
  ll mid = (l+r)/2;
  ll cur = INF, best = -1;
  for(int i = min(mid,optr) ; i >= optl ; i--){
  	ll b = v[mid][1];
  	ll a = v[i][0];
  	ll d = (i > 1 ? v[i - 1][0] : -INF);
    if(dp[i-1] + (b-a+1) * (b-a+1) + max(0LL,d-a+1) * max(0LL,d-a+1) < cur){
      best = i;
      cur = dp[i-1] + (b-a+1) * (b-a+1) + max(0LL,d-a+1) * max(0LL,d-a+1);
    }
  }
  ndp[mid] = cur;
  f(l,mid-1,optl,best) , f(mid+1,r,best,optr);
}

ll take_photos(int n,int m,int k,vector<int> r,vector<int> c){
  
  ll ans = INF;

  for(int i=0;i<n;i++){
  	ll a=r[i],b=c[i];
  	if(a>b) swap(a,b);
  	v.push_back({a,b});
  }	

  sort(all(v));
  vector<array<ll,2>> xdd;
  xdd.push_back({-1LL,-1LL});
  for(int i=0;i<n;i++){
  	if(v[i][0] == xdd.back()[0]){
  	  xdd.pop_back();
  	  xdd.push_back(v[i]);
  	}
  	else if(xdd.back()[1] < v[i][1]) xdd.push_back(v[i]);
  }  
  swap(v,xdd);

  n = sz(v) - 1;

  dp.assign(n+5,INF);
  dp[0] = 0;

  for(int i=1;i<=k;i++){
    ndp.assign(n+5,INF);
    f(1,n,1,n);
    swap(dp,ndp);
    ans=min(ans,dp[n]);
  }
  
  return ans;
}

/*void _(){
  int n,m,k;
  cin >> n >> m >> k;
  for(int i=0;i<n;i++){
  	int a,b;
  	cin >> a >> b;
  	if(a>b) swap(a,b);
  	v.push_back({a,b});
  }	
  
  ll ans = INF;
  sort(all(v));
  vector<array<ll,2>> xdd;
  xdd.push_back({-1LL,-1LL});
  for(int i=0;i<n;i++){
  	if(v[i][0] == xdd.back()[0]){
  	  xdd.pop_back();
  	  xdd.push_back(v[i]);
  	}
  	else if(xdd.back()[1] < v[i][1]) xdd.push_back(v[i]);
  }  
  swap(v,xdd);

  n = sz(v) - 1;

  dp.assign(n+5,INF);
  dp[0] = 0;
   
  for(int i=1;i<=k;i++){
    ndp.assign(n+5,INF);
    f(1,n,1,n);
    swap(dp,ndp);
    ans=min(ans,dp[n]);
  }
  
  cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

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