Submission #1114934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114934		mat_jur	Aliens (IOI16_aliens)	C++17	100 / 100	270 ms	7068 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else 
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
using ld = long double;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
 
const ll inf = 1e15;

ll sq(int x) {
	return ll(x)*x;
}

struct line {
	ll a, b;
	int c;
	line(ll x = 0, ll y = 0, int z = 0): a(x), b(y), c(z) {}
};

ld intersection(line l1, line l2) {
	assert(l1.a != l2.a);
	return ld(l2.b - l1.b) / ld(l1.a - l2.a);
}

struct CHT {
	deque<line> q;
	CHT() {}

	void add(line l) {
		while (ssize(q) >= 2 && intersection(l, q[ssize(q)-2]) <= intersection(q[ssize(q)-2], q[ssize(q)-1])) q.pop_back();
		q.eb(l);
	}

	pair<ll, int> query(ll x) {
		if (!ssize(q)) return mp(inf, 0);
		while (ssize(q) >= 2 && x >= intersection(q[0], q[1])) q.pop_front();

		return mp(q[0].a * x + q[0].b, q[0].c);
	}
};
 
long long take_photos(int n, int m, int k, std::vector<int> x, std::vector<int> y) {
	for (int i = 0; i < n; ++i)
		if (x[i] > y[i]) swap(x[i], y[i]);
 
	debug(x);
	debug(y);
 
	vector<int> nx, ny;
 
	vector<int> idx(n);
	iota(all(idx), 0);
	sort(all(idx), [&](int a, int b) {
		return mp(y[a], x[a]) > mp(y[b], x[b]);
	});
 
	debug(idx);
 
	int mx = m+1;
	for (int i : idx) {
		if (mx <= x[i]) continue;
		debug(i);
		debug(mx);
		debug(mp(x[i], y[i]));
		nx.eb(x[i]); ny.eb(y[i]);
		mx = x[i];
	}
 
	n = ssize(nx);
	x = nx; y = ny;
	reverse(all(x));
	reverse(all(y));
 
	debug(n);
	debug(x);
	debug(y);
 
	auto solve_lambda = [&](ll lambda) {
		vector<pair<ll, int>> dp(n+1);
		dp[0] = mp(0, 0);

		CHT cht;
		for (int i = 1; i <= n; ++i) {
			cht.add(line(-2 * (x[i-1]-1), sq(x[i-1]-1) + dp[i-1].fi - (i - 2 >= 0 ? sq(max(0, y[i-2] - x[i-1]+1)) : 0ll), dp[i-1].se));
			dp[i] = cht.query(y[i-1]);
			dp[i].fi += sq(y[i-1]) + lambda;
			dp[i].se++;
		}
	 
		return dp[n];
	};

	ll low = 0, high = LONG_MAX/2;

//	for (int l = 0; l <= 10; ++l) {
//		debug(l);
//		debug(solve_lambda(l));
//		cerr << '\n';
//	}

	while (high - low > 1) {
		ll mid = (high + low) / 2;
		auto [u, c] = solve_lambda(mid);
		debug(mp(mid, mp(u, c)));
		if (c <= k) high = mid;
		else low = mid;
	}

	debug(low);
	debug(high);
	debug(solve_lambda(low));
	debug(solve_lambda(high));
	auto [u, c] = solve_lambda(low);
	debug(mp(u, c));
 
    return u - k * low;
}
 
#ifdef LOCAL
int main() {
    int n, m, k;
    assert(3 == scanf("%d %d %d", &n, &m, &k));
    std::vector<int> r(n), c(n);
    for (int i = 0; i < n; i++) {
        assert(2 == scanf("%d %d", &r[i], &c[i]));
    }
    long long ans = take_photos(n, m, k, r, c);
    
    
    printf("%lld\n", ans);
}
#endif

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