Submission #748557

#	Time	Username	Problem	Language	Result	Execution time	Memory
748557		AnhPham	Aliens (IOI16_aliens)	C++17	Compilation error	0 ms	0 KiB

aliens

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...)42
#endif

#define int                  long long
#define SZ(_v)               (int)(_v).size()
#define all(_v)              (_v).begin(), (_v).end()
#define pb                   push_back

#define FOR(_v, _l, _r)      for (int _v = _l; _v <= _r; ++_v)
#define FOD(_v, _r, _l)      for (int _v = _r; _v >= _l; --_v)
#define REP(_v, _r)          for (int _v = 0; _v < _r; ++_v)
#define RED(_v, _r)          for (int _v = _r - 1; _v >= 0; --_v)

const   int N   =            (int)1e6 + 1, M = (int)1e3 + 1;
const   int MOD =            (int)1e9 + 7;

typedef pair<int, int>       ii;
typedef pair<int, ii>        pii;
#define f first
#define s second

void solve();

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    solve();
}

int n, m, k;
ii a[N], dp[N];
pii l[N];
int s, e, cnt;

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

bool cp(pii x, pii y, pii z) {
	return (x.s.f - z.s.f) * (y.s.s - x.s.s) >= (x.s.f - y.s.f) * (z.s.s - x.s.s);
}

int f(int x, int y) {
	return l[x].s.f * y + l[x].s.s;
}

void update(int x, int y, int z) {
	while (e - s > 1 && cp(l[e - 2], l[e - 1], { z, { x, y } }))
        --e;

	l[e++] = { z, { x, y } };
}

ii calc(int x) {
	s = e = 0;
	update(-2 * (a[0].f - 1), sq(a[0].f - 1), 0);
	FOR(i, 1, cnt) {
		while (e - s > 1 && f(s, a[i - 1].s) >= f(s + 1, a[i - 1].s)) 
            ++s;

		dp[i] = { f(s, a[i - 1].s) + sq(a[i - 1].s) + x, dp[l[s].f].s + 1 };
		update(-2 * (a[i].f - 1), dp[i].f + sq(a[i].f - 1) - sq(max(0ll, a[i - 1].s - a[i].f + 1)), i);
	}

	return dp[cnt];
}

int take_photos(vector<int> x, vector<int> y) {
	REP(i, n) 
        a[i] = { min(x[i], y[i]), max(x[i], y[i]) };
	
	sort(a, a + n, [&](ii x, ii y) {
		return x.f == y.f ? x.s > y.s : x.f < y.f;
	});
	
    cnt = 1;
	FOR(i, 1, n - 1) 
        if(a[i].s > a[cnt - 1].s)
            a[cnt++] = a[i];
	
	int l = 0, r = sq(m);
	while(r - l > 1) {
		int mid = (l + r) / 2;
		k <= calc(mid).s ? l = mid : r = mid;
	}
	
	return calc(l).f - k * l;
}

void solve() {
	cin >> n >> m >> k;
	
	vector<int> x(n), y(n);
	REP(i, n) 
        cin >> x[i] >> y[i];
	
	cout << take_photos(x, y);
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc6sTwoj.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccZJAzPl.o:aliens.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc6sTwoj.o: in function `main':
grader.cpp:(.text.startup+0xf0): undefined reference to `take_photos(int, int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status