Submission #172668

#	Time	Username	Problem	Language	Result	Execution time	Memory
172668		figter001	Aliens (IOI16_aliens)	C++17	41 / 100	2035 ms	4080 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int n,k;
vector<pair<int,int>> segments;
vector<ll> rem;
int cnt;

pair<ll,ll> calc(ll cst){
	vector<pair<ll,ll>> dp = vector<pair<ll,ll>> (cnt,{1e18,1e18});
	for(int i=0;i<cnt;i++){
		for(int j=i;j>=0;j--){
			pair<ll,ll> nxt = (j ? dp[j-1]  : make_pair(0ll,0ll));
			int fr = segments[j].first;
			int to = segments[i].second;
			ll add = to - fr + 1;
			add *= add;
			add -= rem[j];
			if(nxt.first <= ll(1e18) - add - cst){
				nxt.first += add+cst;
				nxt.second++;
				dp[i] = min(dp[i] , nxt);
			}
		}
	}
	return dp[cnt-1];
}

ll find_answer(){
	ll md,lo=1,hi=1e15,lamda = -1;
	pair<ll,ll> tst = calc(0);
	if(tst.second <= k)return tst.first;
	while(lo <= hi){
		md = (lo + hi)/2;
		ll used = calc(md).second;
		if(used <= k){
			hi = md-1;
			lamda = md;
		}else{
			lo = md+1;
		}
	}
	assert(lamda != -1);
	pair<ll,ll> ans = calc(lamda);
	return ans.first - lamda * k;
}


ll take_photos(int N,int m,int K,vector<int> R, vector<int> C){
	n = N;k = K;
	vector<pair<int,int>> tmp;
	for(int i=0;i<n;i++){
		int r = R[i];
		int c = C[i];
		tmp.push_back({max(r,c) , min(r,c)});
	}
	sort(tmp.begin(),tmp.end());
	set<pair<int,int>> st;
	for(int i=0;i<n;i++){
		int l = tmp[i].second;
		int r = tmp[i].first;
		while(st.size() && -st.begin()->first >= l){
			st.erase(st.begin());
		}
		st.insert({-l,r});
	}
	while(st.size()){
		pair<int,int> it = *st.begin();
		st.erase(st.begin());
		it.first = -it.first;
		// cout << it.first << ' ' << it.second << endl;
		segments.push_back(it);
	}
	reverse(segments.begin(),segments.end());
	cnt = segments.size();
	rem.resize(cnt);

	for(int i=1;i<cnt;i++){
		int fr = segments[i].first;
		int bf = segments[i-1].second;
		if(bf >= fr){
			rem[i] = bf - fr + 1;
			rem[i] *= rem[i];
		}
	}

	ll ans = find_answer();
	return ans;
}

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