Submission #1247844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247844		shidou26	Aliens (IOI16_aliens)	C++20	Compilation error	0 ms	0 KiB

aliens

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

#define endl '\n'
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define filter(v) v.resize(unique(all(v)) - v.begin())
#define dbg(x) "[" #x " = " << (x) << "]"
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> bool maximize(T &a, T b) {
    if(a < b) {
        a = b;
        return true; 
    }else return false;
}
template<typename T> bool minimize(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }else return false;
}
template<typename T> T rnd(T a, T b) {
    return uniform_int_distribution<T>(a, b)(rng);
}

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<long long, int> li;

const int N = 1e5 + 3;

int n, m, k;
int r[N], c[N];

pair<int, int> a[N];
li dp[N];

ll square(int x) {
	return 1LL * x * x;
}

void better(li &x, li y) {
	if(x.first == y.first) maximize(x, y);
	else minimize(x, y);
}

li f(ll lambda) {
	dp[1] = li(square(a[1].second - a[1].first) + lambda, 1);
	for(int i = 2; i <= n; i++) {
		dp[i] = li(LLONG_MAX, 0);
		for(int j = 1; j < i; j++) {
			better(dp[i], ii(
				dp[j].first + square(a[i].second - a[i].first) - square(a[j].second - a[i].first) + lambda,
				dp[j].second + 1
			));	
		}
	}

	return dp[n];
}

ll process() {
	vector<ii> segments;
	for(int i = 1; i <= n; i++) {
		segments.emplace_back(min(r[i], c[i]), max(r[i], c[i]));
	}

	sort(all(segments), [&](ii a, ii b){
		return (a.first == b.first ? a.second > b.second : a.first < b.first);
	});

	vector<ii> tmp;
	for(auto [l, r] : segments) {
		if(tmp.empty() || tmp.back().second < r) 
			tmp.emplace_back(l, r);
	}

	n = sz(tmp);
	for(int i = 1; i <= n; i++) {
		a[i] = tmp[i - 1]; 
		a[i].first--;
	}

	ll l = 1, r = 1LL * m * m, result = 0;
	while(l <= r) {
		ll mid = (l + r) >> 1;
		if(f(mid).second >= k) result = mid, l = mid + 1;
		else r = mid - 1;
	}

	return f(result).first - k * result;
	return 0;
}

ll take_photos(int _n, int _m, int _k, int _r[], int _c[]) {
	n = _n; 
	m = _m;
	k = _k;

	for(int i = 1; i <= n; i++) {
		r[i] = _r[i - 1] + 1;
		c[i] = _c[i - 1] + 1;
	}

	return process();
}

Compilation message (stderr)

aliens.cpp:1:10: fatal error: aliens.h: No such file or directory
    1 | #include <aliens.h>
      |          ^~~~~~~~~~
compilation terminated.
aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~