Submission #82109

#	Time	Username	Problem	Language	Result	Execution time	Memory
82109		Batrr	Aliens (IOI16_aliens)	C++14	0 / 100	2051 ms	560 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;
	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);
	}
	ll get(ll x){
		if(v.empty())
			return INF;
		ptr = min(ptr, (int)v.size());
		while(ptr < v.size()){
			if(v[ptr].X < x)
				ptr++;
		}
		ll res = v[ptr - 1].k * x + v[ptr - 1].b;
		return res;
	}

};
ll sqr(ll x){
	return x * x;
}
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();
	vector< ll > dp(n, INF);   
	vector< line > ln(n, {0, INF});
	ll ans = INF;

	for(int q = 1; q <= k ; q++){
    	cvh btr;
    	for(int i = 0; i < n; i++){
    		dp[i] = min(sqr(arr[i].s - arr[0].f + 1), sqr(arr[i].s) + btr.get(arr[i].s)); 
    		btr.add(ln[i]);
    		if(i != n - 1){
            	ll b = dp[i] + 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, b};
    		}
    	}

    	if(ans > dp[n - 1])
    		ans = dp[n - 1];
	}
    return ans;
}

Compilation message (stderr)

aliens.cpp: In member function 'll cvh::get(ll)':
aliens.cpp:51:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr < v.size()){
         ~~~~^~~~~~~~~~

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