Submission #82132

#	Time	Username	Problem	Language	Result	Execution time	Memory
82132		Batrr	Aliens (IOI16_aliens)	C++14	100 / 100	582 ms	41264 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 

using namespace std;                    

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = (int)1e5 + 123, inf = 1e9;
const ll INF = 1e18;

using namespace std;

struct line{
	ll k, b;
	double X;
	int cnt;
	double intersect(line a){
		return -1.0 * (a.b - b) / (a.k - k);
	}
};
struct cvh{
	vector< line > v;
	int ptr = 0;
	void add(line x){
		while(v.size() > 1){
			line a = v[v.size() - 1];
			line b = v[v.size() - 2];
			if(x.intersect(a) < x.intersect(b))
				v.pop_back();
			else
				break;
		}
		if(v.empty()){
			x.X = -INF;
		}else{
			line a = v.back();
			x.X = x.intersect(a);          	
		}
		v.pb(x);
	}
	pair<ll, ll> get(ll x, ll add){
		if(v.empty())
			return {INF, 1};
		ptr = min(ptr, (int)v.size());
		while(ptr < v.size() && v[ptr].X < x)
				ptr++;
		pair< ll, ll> res;
		res.f = v[ptr - 1].k * x + v[ptr - 1].b;
		res.s = v[ptr - 1].cnt + 1;
		res.f += add;
		return res;
	}

};
ll sqr(ll x){
	return x * x;
}
pair<ll ,ll> get(ll C, vector< pair<int, int> > &arr){
	int n = arr.size();
	vector< pair<ll, ll> > dp(n);   
	vector< line > ln(n, {0, INF});
   
    cvh btr;

    for(int i = 0; i < n; i++){
    	
    	dp[i] = min( mp(sqr(arr[i].s - arr[0].f + 1), 1ll) , btr.get(arr[i].s, sqr(arr[i].s)) );
    	dp[i].f += C; 
    	
    	if(i != n - 1){
           	ll b = dp[i].f + sqr(arr[i + 1].f - 1) - sqr(max(0, arr[i].s - arr[i + 1].f + 1));
    		ll k = - 2 * (arr[i + 1].f - 1);
    		ln[i].k = k;
    		ln[i].b = b;
    		ln[i].cnt = dp[i].s;
    		btr.add(ln[i]);
    	}                  	
    }                
	return dp[n - 1];
}
ll take_photos(int n, int m, int k, vector<int> row, vector<int> col) {
	vector< pii > arr, tmp;
	
	for(int i = 0; i < n; i++){
		int l, r;
		l = row[i];
		r = col[i];
		if(l > r)
			swap(l, r);	
		tmp.pb({l, -r});
	}
	sort(tmp.begin(), tmp.end());
	for(int i = 0, mx = -1; i < n; i++){
		int l = tmp[i].f;
		int r = -tmp[i].s;
		if(r <= mx)
			continue;
		mx = r;
		arr.pb({l, r});
	}
	n = arr.size();
	if(n < k)
		k = n;
	ll l = 0, r = 1e15;
	
	while(l <= r){
		ll m = (l + r) / 2;
		int x = get(m, arr).s;
		if(x > k)
			l = m + 1;
    	else
    		r = m - 1;
    }
    r++;
    return get(r, arr).f - k * r;
}

Compilation message (stderr)

aliens.cpp: In member function 'std::pair<long long int, long long int> cvh::get(ll, ll)':
aliens.cpp:52:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr < v.size() && v[ptr].X < x)
         ~~~~^~~~~~~~~~

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