Submission #104868

#	Time	Username	Problem	Language	Result	Execution time	Memory
104868		minson123	Aliens (IOI16_aliens)	C++11	0 / 100	5 ms	2716 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;
	}
};
struct Line{
	ll a,b;
	int idx;
	Line(ll _a=0,ll _b=0,int _idx=0):a(_a),b(_b),idx(_idx){}
} dq[maxn];
inline bool check(Line l,Line l2,Line l3){
	ll a1=l.a,b1=l.b;
	ll a2=l2.a,b2=l2.b;
	ll a3=l3.a,b3=l3.b;
	return (__int128)(a2-a3)*(b3-b1)>(__int128)(b3-b2)*(a1-a3);
}
inline ll get_val(ll x,Line l){
	return x*l.a+l.b;
}
pli dp[maxn];
vector<Section> sec,tmp;
set<int> dic;
bool ban[maxn];
inline int calc_dp(ll ext){
	dp[0]=pli(0,0);
	int head=0,rear=0;
	dq[rear++]=Line(-2ll*sec[0].l,(ll)sec[0].l*sec[0].l,0);
	for(int i=1;i<=(int)sec.size();i++){
		/*while(head+1<rear && get_val(sec[i-1].r+1,dq[head])>get_val(sec[i-1].r+1,dq[head+1])) head++;
		dp[i].first=get_val(sec[i-1].r+1,dq[head])+(ll)(sec[i-1].r+1)*(sec[i-1].r+1)+ext;
		dp[i].second=dp[dq[head].idx].second+1;
		if(i<(int)sec.size()){
			Line ln=Line(-2ll*sec[i].l,(ll)sec[i].l*sec[i].l-max(0ll,(ll)(sec[i-1].r-sec[i].l+1)*(sec[i-1].r-sec[i].l+1))+dp[i].first,i);
			while(head+1<rear && check(dq[rear-2],dq[rear-1],ln)) rear--;
			dq[rear++]=ln;
		}*/
		dp[i].first=1ll<<62;
		dp[i].second=100001;
		for(int j=0;j<i;j++){
			ll v=dp[j].first+(ll)(sec[i-1].r+1-sec[j].l)*(sec[i-1].r+1-sec[j].l)-(j==0?0ll:max(0ll,(ll)(sec[j-1].r+1-sec[j].l)*(sec[j-1].r+1-sec[j].l)))+ext;
			int t=dp[j].second+1;
			pli pr=pli(v,t);
			if(pr<dp[i]){
				dp[i]=pr;
			}
		}
	}
	return dp[(int)sec.size()].second;
}
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++){
		Section s=Section(r[i],c[i]);
		if(s.l>s.r) swap(s.l,s.r);
		sec.push_back(s);
	}
	sort(sec.begin(),sec.end());
	sec.erase(unique(sec.begin(),sec.end()),sec.end());
	/*int sz=0;
	for(int i=0;i<(int)sec.size();i++)
		if(sec[sz-1].r<sec[i].r) sec[sz++]=sec[i];
	sec.erase(sec.begin()+sz,sec.end());*/
	k=min(k,(int)sec.size());
	ll L=0,R=m*m+10;
	while(L!=R){
		ll mid=(L+R)>>1;
		if(calc_dp(mid)<=k) R=mid;
		else L=mid+1;
	}
	calc_dp(R);
	pli q1=dp[(int)sec.size()];
	calc_dp(R-1);
	pli q2=dp[(int)sec.size()];
	if(q1.second==k){
		return q1.first-R*k;
	}else{
		ll diff=(__int128)((q1.first-q1.second*R)-(q2.first-q2.second*(R-1)))*(__int128)(k-q1.second)/(__int128)(q2.second-q1.second);
		return q1.first-R*q1.second-diff;
	}
}

Compilation message (stderr)

aliens.cpp: In function 'int calc_dp(ll)':
aliens.cpp:37:6: warning: unused variable 'head' [-Wunused-variable]
  int head=0,rear=0;
      ^~~~

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