Submission #104873

#	Time	Username	Problem	Language	Result	Execution time	Memory
104873		minson123	Aliens (IOI16_aliens)	C++11	12 / 100	10 ms	512 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> pli;
const int maxn=100010;
struct Section{
	int l,r;
	Section(int _l=0,int _r=0):l(_l),r(_r){}
	inline bool operator<(const Section& rhs) const{
		return l!=rhs.l?l<rhs.l:r>rhs.r;
	}
	inline bool operator==(const Section& rhs) const{
		return l==rhs.l && r==rhs.r;
	}
};
vector<Section> sec;
pli dp[maxn];
inline pli calc_dp(ll ext){
	dp[0]=pli(0,0);
	for(int i=1;i<=(int)sec.size();i++){
		dp[i]=pli(1ll<<62,100001);
		for(int j=1;j<=i;j++){
			pli pr=pli(dp[j-1].first+(ll)(sec[i-1].r-sec[j-1].l)*(sec[i-1].r-sec[j-1].l)+ext,dp[j-1].second+1);
			if(pr<dp[i]) dp[i]=pr;
		}
	}
	return dp[(int)sec.size()];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	for(int i=0;i<n;i++){
		if(r[i]>c[i]) swap(r[i],c[i]);
		sec.push_back(Section(r[i],c[i]+1));
	}
	sort(sec.begin(),sec.end());
	sec.erase(unique(sec.begin(),sec.end()),sec.end());
	k=min(k,(int)sec.size());
	ll L=0,R=(ll)m*m+10;
	while(L!=R){
		ll mid=(L+R)>>1;
		if(calc_dp(mid).second<=k) R=mid;
		else L=mid+1;
	}
	return calc_dp(R).first-R*k;
}

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