제출 #348327

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
348327		Sparky_09	Aliens (IOI16_aliens)	C++17	100 / 100	186 ms	8928 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
const ll N = 100005, inf = 1e12;
 
 
/*
//kactl CHT template
struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};

struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) {
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	ll query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return l.k * x + l.m;
	}
};
*/

ll n, m, k;
pair<ll,ll> dt[N];
 
vector<pair<ll,ll>> mainl, a;
 
//note class has stuff private by default, struct has public
//just use struct 
struct hull{
	deque<pair<pair<ll,ll>, ll>> v;
	void clear() {v.clear();}
	bool aok(pair<ll,ll> &A, pair<ll,ll> &B, pair<ll,ll> &C){
		return (B.Y - A.Y) * (A.first - C.first) < (C.Y - A.Y) * (A.first - B.first);
	}
	ll val(pair<ll,ll> &T, ll P) {return T.first*P+T.Y;}
	void upd (pair<pair<ll,ll>, ll> A){
		for(ll i=v.size();i-->1;) {
			if(aok(v[i-1].first, v[i].first, A.first)) break;
			else v.pop_back();
		}
		v.push_back(A);
	}
	pair<ll,ll> get(ll P){
		while(v.size() > 1) {
			if(val(v[0].first, P) <= val(v[1].first, P)) break;
			else v.pop_front();
		}
		return pair<ll,ll>(val(v[0].first, P), v[0].second+1);
	}
} h;
 
ll sq(ll first) {return (ll)((ll)first*(ll)first);}
 
pair<ll,ll> solve(ll L){
	h.clear();
	h.upd({pair<ll,ll>(-2*(a[0].first-1), sq(a[0].first-1) + L), 0});
	for(ll i = 0; i<n; i++){
		auto T = h.get(a[i].second);
		dt[i] = {T.first + sq(a[i].second), T.second};
		if(i == n) continue;
		h.upd({{-2*(a[i+1].first-1), sq(a[i+1].first-1) - sq(max(0ll, a[i].second-a[i+1].first+1)) + dt[i].first + L}, T.second});
	}
	return dt[n-1];
}
 
ll take_photos(int nn, int mm, int kk, vector<int> r, vector<int> c) {
	m = mm; k = kk;
	for(ll i = 0 ; i<nn; i++) {
		if(r[i] < c[i]) mainl.push_back(pair<ll,ll>(r[i], c[i]));
		else mainl.push_back(pair<ll,ll>(c[i], r[i]));
	}
	sort(mainl.begin(), mainl.end());
	for(auto &T : mainl) {
		if(a.empty() or a.back().second < T.second) a.push_back(T);
	}
	n = a.size();
	ll S = 0, E = inf;
	while(S < E) {
		ll M = (S+E)/2;
		solve(M).second <= k ? E = M : S = M+1;
	}
	return solve(S).first - k * S;
}
/*
ll sq(ll first) {return (ll)((ll)first*(ll)first);}
ll val(pair<ll,ll> &aa, ll bb) {return aa.first*bb+aa.second;}

                                                 
pair<ll,ll> solve (ll L) {
	deque<pair<pair<ll,ll>, ll>> v;
	v.clear();
	pair<pair<ll,ll>,ll> to_upd = {{-2*(a[0].first-1), sq(a[0].first-1) + L}, 0};
	//upd
	v.push_back(to_upd);
	for(ll i = 0; i < n; i++) {
		while(v.size() > 1){
			if(val(v[0].first, a[i].second) <= val(v[1].first, a[i].second)) break;
			else v.pop_front();
		}
		pair<ll,ll> getit = {val(v[0].first, P), v[0].second+1};
		vpp[i] = {T.first + sq(a[i].second), T.second};
		//
	}
	return vpp[n-1];
}
 

*/

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