Submission #1104102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104102		alexander707070	Aliens (IOI16_aliens)	C++14	4 / 100	7 ms	2668 KiB

aliens

#include<bits/stdc++.h>

#define MAXN 100007
using namespace std;

const long long inf=1e13,inff=1e18;

long long dp[MAXN];
int cnt[MAXN];

struct interval{
	int l,r;

	inline friend bool operator < (interval fr,interval sc){
		if(fr.l==sc.l)return fr.r>sc.r;
		return fr.l<sc.l;
	}
}s[MAXN],w[MAXN];

int n,m,k,sz;

long long area(long long l,long long r){
	if(l>r)return 0;

	return (r-l+1)*(r-l+1);
}

long long cost(int l,int r){
	return area(w[l].l,w[r].r) - area(w[l].l,w[l-1].r);
}

void solve(long long delta){
	for(int i=1;i<=sz;i++){
		dp[i]=inff;

		for(int t=i;t>=1;t--){
			if(dp[t-1]+cost(t,i)+delta<dp[i]){
				dp[i]=dp[t-1]+cost(t,i)+delta;
				cnt[i]=cnt[t-1]+1;

			}else if(dp[t-1]+cost(t,i)+delta==dp[i] and cnt[t-1]+1<cnt[i]){
				cnt[i]=cnt[t-1]+1;
			}
		}
	}
}

long long bin(){
	long long l=-1,r=inf,tt;

	while(l+1<r){
		tt=(l+r)/2;

		solve(tt);

		if(cnt[sz]>k){
			l=tt;
		}else{
			r=tt;
		}
	}

	solve(r);
	return dp[sz]-cnt[sz]*r;
}

long long take_photos(int N, int M, int K, vector<int> r, vector<int> c){
	n=N; m=M; k=K;

	for(int i=1;i<=n;i++){
		s[i]={min(r[i-1],c[i-1])+1,max(r[i-1],c[i-1])+1};
	}

	sort(s+1,s+n+1);

	for(int i=1;i<=n;i++){
		if(sz>0 and s[i].r<=w[sz].r)continue;
		sz++; w[sz]=s[i];
	}

	return bin();
}

/*int main(){

	cout<<take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6})<<"\n";

	return 0;
}*/

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