Submission #204540

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

aliens

#include "aliens.h"

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define f first
#define se second
#define int long long
#define pll pair<ll, ll>
#define pii pair<int, int>


using namespace std;

//const int N = 2e5 + 123;
const int N = 3e3 + 123;
const int M = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll inf = 1e16;


struct segment{
	ll l, r, l1, r1;
	segment(ll l, ll r, ll l1, ll r1) : l(l), r(r), l1(l1), r1(r1) {};
};


ll L[N], R[N], Lto[N], Rto[N], ar[N], sz = 0;
bool isworth[N];
vector <segment> worth;
vector <ll> byl[N];
unordered_set <ll> st[M];
ll dp[N][N];


bool cmp(segment x, segment y) {
	return x.r < y.r;
}


ll cost(ll l, ll r) {
	if (l > r)
		return 0;
	return (r - l + 1) * (r - l + 1);
}


ll take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
	if (n > 505 || m > 1005)
		return 0;
	int tmp = 0;
	for (int i = 0; i < n; i++) {
		if (c[i] >= r[i]) {
			if (st[r[i] + 1].count(c[i] + 1))
				continue;
			tmp++;
			L[tmp] = r[i] + 1;
			R[tmp] = c[i] + 1;
		} else {
			if (st[c[i] + 1].count(r[i] + 1))
				continue;
			tmp++;
			L[tmp] = c[i] + 1;
			R[tmp] = r[i] + 1;
		}
//		if (L[tmp] == 4 && R[tmp] == 5) {
//			cout << i << " " << r[i] + 1 << " " << c[i] + 1 << endl;
//			cout << endl;
//		}
		st[L[tmp]].insert(R[tmp]);
		ar[++sz] = L[tmp];
		ar[++sz] = R[tmp];
	}
	n = tmp;
	
//	for (int i = 1; i <= n; i++)
//		cout << i << " " << L[i] << " " << R[i] << endl;
//	cout << endl;
	
	sort(ar + 1, ar + sz + 1);
	ll t = unique(ar + 1, ar + sz + 1) - ar - 1;
	for (int i = 1; i <= n; i++) {
		Lto[i] = lower_bound(ar + 1, ar + t + 1, L[i]) - ar;		
		Rto[i] = lower_bound(ar + 1, ar + t + 1, R[i]) - ar;
		byl[Lto[i]].pb(i);
		isworth[i] = true;
	}
	ll curmax = 0;
	for (int i = 1; i <= 2 * n; i++) {
		ll localmx = 0;
		for (int to : byl[i]) {
			localmx = max(localmx, Rto[to]);
			if (Rto[to] <= curmax)
				isworth[to] = false;
		}
		for (int to : byl[i])
			if (Rto[to] < localmx)
				isworth[to] = false;
		curmax = max(curmax, localmx);
	}
	
//	for (int i = 1; i <= n; i++)
//		cout << i << " " << isworth[i] << endl;

	worth.pb({-1, -1, -1, -1});

	for (int i = 1; i <= n; i++) {
		if (isworth[i])
			worth.pb({L[i], R[i], Lto[i], Rto[i]});
	}
	n = worth.size() - 1;
	sort(worth.begin(), worth.end(), cmp);
	
	for (int i = 1; i <= n; i++)
		dp[1][i] = cost(worth[1].l, worth[i].r);
	
	ll ans = dp[1][n];
	
	for (int x = 2; x <= min(n, k); x++) {
		for (int i = 1; i < k; i++)
			dp[x][i] = inf;
		for (int i = k; i <= n; i++) {
			dp[x][i] = inf;
			for (int j = 1; j < i; j++)
				dp[x][i] = min(dp[x][i], dp[x - 1][j] + cost(worth[j + 1].l, worth[i].r) - cost(worth[j + 1].l, worth[j].r));
		}
		ans = min(ans, dp[x][n]);
	}
	
	return ans;
}


//main() {
//	ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL);
//	freopen("input.txt", "r", stdin);
//	int n, m, k; vector <int> r, c;
//	r.clear(); c.clear();
//	cin >> n >> m >> k;
//	for (int i = 1; i <= n; i++) {
//		int x, y;
//		cin >> x >> y;
////		cout << x << " " << y << endl;
//		r.pb(x);
//		c.pb(y);
//	}
//	cout << take_photos(n, m, k, r, c);
//	return 0;
//}

Compilation message (stderr)

/tmp/ccVqNsdn.o: In function `main':
grader.cpp:(.text.startup+0xdf): 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