Submission #172819

#	Time	Username	Problem	Language	Result	Execution time	Memory
172819		figter001	Aliens (IOI16_aliens)	C++17	Compilation error	0 ms	0 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

#define debug(x) '[' << #x << " is: " << x << "] "
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const ll oo = 1e18;

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

struct con{
	int l,used;
	ll prev;
	con(int left,int uu,ll pp){
		l = left;used = uu;prev = pp;
	}

	pair<ld,int> getcost(ld x){
		ld d = l-x;
		return {d*d + prev ,used};
	}

	ld tover(con rhs){
		ld l1 = l,l2 = rhs.l;
		ld c = prev - rhs.prev;
		ld all = l1*l1 - l2 * l2 + c;
		ld rem = 2 * l1 - 2 * l2;
		all /= rem;
		return all;
	}
};

pair<ll,ll> calc(ll cst){

	pair<ll,int> curbest = {0,0};
	int fptr=0,bptr=0;
	vector<con> bag(cnt+2,con(0,0,0));

	for(int i=0;i<cnt;i++){
		int l = segments[i].first;
		int r = segments[i].second;
		con nxt = con(l-1,curbest.second+1,curbest.first + cst-rem[i]);
		while(bptr - fptr >= 2 && bag[bptr-2].tover(bag[bptr-1]) >= bag[bptr-2].tover(nxt))bptr--;
		bag[bptr++] = nxt;
		while(fptr + 1 < bptr && bag[fptr].getcost(r) >= bag[fptr+1].getcost(r))fptr++;
		curbest = bag[fptr].getcost(r);
	}
	return curbest;
}

ll find_answer(){
	ll md,lo=0,hi=1e11,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 solve(int N,int m,int K,vector<pair<int,int>> a){
	n = N;k = K;
	vector<pair<int,int>> tmp;
	for(int i=0;i<n;i++){
		int r = a[i].first;
		int c = a[i].second;
		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);
	}
	sort(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;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(10);
	cout << fixed;
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
	#endif
	int n,m,k;
	cin>>n>>m>>k;
	vector<pair<int,int>> a(n);
	for(int i=0;i<n;i++)cin>>a[i].first>>a[i].second;
	cout << solve(n,m,k,a) << endl;
}

Compilation message (stderr)

aliens.cpp: In function 'int main()':
aliens.cpp:124:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen("input.txt","r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/tmp/cc9nOo0Y.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccfMcgnh.o:aliens.cpp:(.text.startup+0x0): first defined here
/tmp/cc9nOo0Y.o: In function `main':
grader.cpp:(.text.startup+0xdf): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status