Submission #285835

#	Time	Username	Problem	Language	Result	Execution time	Memory
285835		eohomegrownapps	Aliens (IOI16_aliens)	C++14	60 / 100	2096 ms	9608 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

ll INF = 1e18;

struct Line{
	ll m = 0;
	ll c = INF;

	Line(ll _m, ll _c){
		m=_m;
		c=_c;
	}
	
	ll f(ll x){
		return m*x + c;
	}

	ld intersectX(Line &a){
		return (1.0*(a.c-c))/(m-a.m);
	}
};

struct ConvexHull{
	deque<Line> dq;

	void insert(Line l){
		// wlog gradients decreasing
		if (dq.size()==0){
			dq.push_back(l);
			return;
		}
		if (dq.back().m == l.m){
			if (l.c < dq.back().c){
				dq.pop_back();
				dq.push_back(l);
			}
			return;
		}
		int s = dq.size();
		while (s>=2 && l.intersectX(dq[s-1])<l.intersectX(dq[s-2])){
			dq.pop_back();
			s--;
		}
		dq.push_back(l);
	}

	ll query(ll x){
		while (dq.size()>=2 && dq[0].f(x)>dq[1].f(x)){
			dq.pop_front();
		}
		return dq[0].f(x);
	}
};

long long take_photos(int n, int m, int k, std::vector<int> rv, std::vector<int> cv) {
    vector<pair<ll,ll>> ptmp(n);
    for (int i = 0; i<n; i++){
    	if (cv[i]>rv[i]){
    		ptmp[i]={rv[i],-cv[i]};
    	} else {
    		ptmp[i]={cv[i],-rv[i]};
    	}
    }
    sort(ptmp.begin(),ptmp.end());
    vector<ll> r;
    vector<ll> c;
    c.push_back(ptmp[0].first);
    r.push_back(-ptmp[0].second);
    for (int i = 1; i<n; i++){
    	if (c.back()<ptmp[i].first&&-r.back()>ptmp[i].second){
    		c.push_back(ptmp[i].first);
    		r.push_back(-ptmp[i].second);
    	}
    }
    /*cout<<"points (monotonically decreasing):\n";
    for (int i = 0; i<c.size(); i++){
    	cout<<c[i]<<' '<<r[i]<<'\n';
    }*/
    n = c.size();
    vector<ll> intersect(n-1);
    for (int i = 0; i<n-1; i++){
    	ll b = r[i];
    	ll a = c[i+1];
    	if (b<a){
    		continue;
    	}
    	//cout<<"intersect "<<a<<' '<<b<<'\n';
    	intersect[i] = (b-a+1) * (b-a+1);
    }
    /*cout<<"intersect values:\n";
    for (int i : intersect){
    	cout<<i<<' ';
    }cout<<'\n';*/

    vector<vector<ll>> dp(2,vector<ll>(n,INF));
    bool cur = 0;
    ll minans = INF;
    for (int num = 1; num<=k; num++){
    	ConvexHull hull;
    	hull.insert({2-2*c[0],(c[0]-1)*(c[0]-1)});
    	for (int x = 0; x<n; x++){
    		dp[cur][x] = r[x]*r[x] + hull.query(r[x]);
    		if (x!=n-1){
    			hull.insert({2-2*c[x+1], dp[!cur][x]-intersect[x]+(c[x+1]-1)*(c[x+1]-1)});
    		} else {
    			minans=min(minans,dp[cur][x]);
    		}
    	}
    	cur=!cur;
    }
    /*for (int num = 1; num<=k; num++){
    	for (int x = 0; x<n; x++){
    		cout<<dp[num][x]<<' ';
    	}cout<<'\n';
    }*/
    return minans;
}

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