Submission #382570

#	Time	Username	Problem	Language	Result	Execution time	Memory
382570		MetalPower	Aliens (IOI16_aliens)	C++14	100 / 100	142 ms	10452 KiB

aliens

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

using namespace std;

#define ll long long
const ll MAXN = 1e5 + 100;
#define pii pair<ll, ll>
#define fi first
#define se second

struct inv{
	ll l; ll r;
};

struct line{
	ll m; ll c; ll cnt;

	ll getY(ll x){
		return m * x + c;
	}
} cht[MAXN];

ll l = 0, r = 1;

bool betterLine(line& a, line& b, line& c){
	ll lhs = (c.c - a.c) * (a.m - b.m), rhs = (b.c - a.c) * (a.m - c.m);
	return lhs < rhs || (lhs == rhs && c.cnt < b.cnt);
}

bool betterQue(line& a, line& b, ll x){
	ll lhs = a.getY(x), rhs = b.getY(x);
	return lhs > rhs || (lhs == rhs && b.cnt < a.cnt);
}

void insertLine(line L){
	while(r - l >= 2 && betterLine(cht[r - 2], cht[r - 1], L))r--;
	cht[r++] = L;
}

pii query(ll x){
	while(r - l >= 2 && betterQue(cht[l], cht[l + 1], x))l++;
	return {cht[l].getY(x), cht[l].cnt};
}

vector<inv> v, grid;

bool cmpGrid(inv& a, inv& b){
	return a.l < b.l || (a.l == b.l && a.r > b.r);
}

void buildVector(){
	sort(grid.begin(), grid.end(), cmpGrid);
	ll sz = grid.size(); inv prev = {-1, -1};
	for(ll i = 0; i < sz; i++){
		if(grid[i].r > prev.r){
			v.push_back(grid[i]); prev = grid[i];
		}
	}
}

void initcht(){
	cht[0] = {-2 * v[0].l + 2, (v[0].l - 1) * (v[0].l - 1), 0};
	l = 0, r = 1;
}

ll memo[MAXN], cnt[MAXN];

pii dp(ll val, ll n){
	memo[0] = cnt[0] = 0;
	initcht(); 
	for(ll i = 1; i <= n; i++){
		pii queAns = query(v[i-1].r);
		memo[i] = queAns.fi + v[i-1].r * v[i-1].r + val;
		cnt[i] = queAns.se + 1;
		if(i < n){
			ll m = -2 * v[i].l + 2, maxim = max((ll)0, (ll)(v[i-1].r - v[i].l + 1));
			ll c = memo[i] - maxim * maxim + (v[i].l - 1) * (v[i].l - 1);
			insertLine({m, c, cnt[i]});
		}
	}
	return {memo[n], cnt[n]};
}

ll take_photos(int a, int b, int c, vector<int> R, vector<int> C) {
	ll n = (ll)a, m = (ll)b, k = (ll)c;
	for(ll i = 0; i < n; i++){
		grid.push_back({(ll)min(R[i], C[i]), (ll)max(R[i], C[i])});
	}
	buildVector();
	ll l = 0, r = 1e12, ans = 0;
	while(l <= r){
		ll mid = (l + r) >> 1;
		pii val = dp(mid, v.size());
		if(val.se <= k){
			ans = val.fi - k * mid, r = mid - 1;
		}
		else l = mid + 1;
	}
	return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:86:16: warning: unused variable 'm' [-Wunused-variable]
   86 |  ll n = (ll)a, m = (ll)b, k = (ll)c;
      |                ^

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