Submission #1326915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326915		Jawad_Akbar_JJ	Aliens (IOI16_aliens)	C++20	100 / 100	139 ms	11244 KiB

aliens

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define ll long long int
const ll N = 1<<17;
ll dp[N], op[N], m[N], c[N], x[N], y[N], M, mx;

ll intersection(ll i, ll j){
	ll A = c[j] - c[i], B = m[i] - m[j];
	return A / B + (A % B != 0);
}

ll sqr(ll A){
	return A * A;
}

pair<ll, ll> profit(ll n, ll Mid){
	vector<ll> v = {0}, st = {0};
	c[0] = x[1] * (x[1] - 2) + 1;

	for (ll i=1;i<=n;i++){
		ll l = 0, r = v.size();
		while (l + 1 < r){
			ll mid = (l + r) >> 1;
			if (st[mid] <= y[i])
				l = mid;
			else
				r = mid;
		}

		l = v[l];
		dp[i] = dp[l] + sqr(y[i] - x[l + 1] + 1) + Mid;
		op[i] = op[l] + 1;

		if (i < n and x[i+1] <= y[i])
			dp[i] -= sqr(y[i] - x[i+1] + 1);
	
		c[i] = dp[i] + x[i+1] * (x[i+1] - 2) + 1;

		while (v.size() > 1 and st.back() >= intersection(v.back(), i))
			v.pop_back(), st.pop_back();
		st.push_back(intersection(v.back(), i));
		v.push_back(i);
	}

	return {dp[n], op[n]};
}

long long take_photos(int n, int mm, int k, vector<int> R, vector<int> C){
	M = mm;
	vector<pair<ll, ll>> vc;

	for (ll i=0;i<n;i++){
		if (R[i] > C[i])
			swap(R[i], C[i]);
		vc.push_back({R[i]+1, C[i]+1});
	}

	sort(begin(vc), end(vc));

	n = 0;
	for (auto [i, j] : vc){
		if (j <= mx)
			continue;
		while (x[n] == i)
			n--;
		n++, x[n] = i, y[n] = j, mx = j;
	}

	for (ll i=1;i<=n;i++)
		m[i-1] = -2 * x[i];

	ll l = 0, r = M * M + 5;
	while (l + 1 < r){
		ll mid = (l + r) / 2;
		if (profit(n, mid).second < k)
			r = mid;
		else
			l = mid;
	}
	auto [a, b] = profit(n, l);
	return a - k * l;
}

Compilation message (stderr)

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
      |         ^~~~

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