Submission #575383

#	Time	Username	Problem	Language	Result	Execution time	Memory
575383		handlename	Aliens (IOI16_aliens)	C++17	12 / 100	87 ms	2260 KiB

aliens

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int MOD=1e9+7;
struct convex{
	deque<pair<long long,long long> > dq;
	long long f(pair<long long,long long> line, long long x){
		return line.first*x + line.second;
	}
	long long qry(long long x){
		/*
		long long res=1e18;
		for (auto i:dq) res=min(res,f(i,x));
		return res;
		*/
		while(dq.size()>1){
			if(f(dq[0],x)>f(dq[1],x)){ //the next line is better
				dq.pop_front(); //remove useless line
			}
			else break;
		}
		return f(dq[0],x);
	}
	long double intersect(long long m1, long long c1, long long m2, long long c2){
		return (long double)(c2-c1)/(m1-m2);
	}
	long double intersect(pair<long long,long long> p1, pair<long long,long long> p2){
		return intersect(p1.first,p1.second,p2.first,p2.second);
	}
	void ins(long long m,long long c) {//insert line y=mx+c
		pair<long long,long long> line = make_pair(m,c);
		while (dq.size()>1) { //to prevent seg fault
			long long s = dq.size();
			if (intersect(dq[s-1], line) <= intersect(dq[s-2], line)){
				dq.pop_back(); //removes useless line
			}
			else break;
		}
		dq.push_back(line);
	}
} *conv;
pair<int,int> brr[200001];
vector<pair<long long,long long> > arr;
long long take_photos(int n,int m,int k,vector<int> r,vector<int> c){
	for (int i=0;i<n;i++){
		r[i]++;
		c[i]++;
		if (r[i]>c[i]) swap(r[i],c[i]); //ri<=ci
		brr[i].first=r[i];
		brr[i].second=c[i];
	}
	sort(brr,brr+n);
	arr.pb(mp(0,0));
	for (int i=0;i<n;i++){
		while (arr.back().first==brr[i].first){
			arr.pop_back();
		}
		if (brr[i].second>arr.back().second){
			arr.pb(brr[i]);
		}
	}
	n=arr.size()-1;
	long long dp[k+1][n+1];
	conv=new convex();
	dp[0][0]=0;
	for (int j=1;j<=n;j++){
		dp[0][j]=1e18;
	}
	for (int i=1;i<=k;i++){
		dp[i][0]=0;
		for (int j=1;j<=n;j++){
			dp[i][j]=dp[i-1][j];
			for (int x=1;x<=j;x++){
				//take square from x to j
				//square is (rx,rx) to (cj,cj)
				long long cur=0;
				cur+=dp[i-1][x-1];
				cur+=(arr[j].second-arr[x].first+1)*(arr[j].second-arr[x].first+1);
				if (arr[x].first<=arr[x-1].second){
					cur-=(arr[x].first-arr[x-1].second+1)*(arr[x].first-arr[x-1].second+1);
				}
				dp[i][j]=min(dp[i][j],cur);
			}
			//cout<<i<<' '<<j<<' '<<dp[i][j]<<'\n';
		}
	}
	return dp[k][n];
}

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