Submission #82124

#	Time	Username	Problem	Language	Result	Execution time	Memory
82124		Batrr	Aliens (IOI16_aliens)	C++14	4 / 100	3 ms	656 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();
	ll l = 0, r = 1e15;
	while(l <= r){
		ll m = (l + r) / 2;
		if(get(m, arr).s > k)
			l = m + 1;
    	else
    		r = m - 1;
    }
    return get(l, arr).f - get(l, arr).s * l;
}

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: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40