Submission #1326631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326631		Jawad_Akbar_JJ	Aliens (IOI16_aliens)	C++20	0 / 100	0 ms	332 KiB

aliens

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

using namespace std;
#define ll long long
const ll N = 1<<17;
ll dp[N][2], r[N], c[N], b[N], m[N];

ll intersection(ll i, ll j){
	ll A = b[j] - b[i], B = m[i] - m[j], pnt = A / B;
	pnt += (A % B != 0);
	// cout<<endl;
	// cout<<b[j]<<" "<<b[i]<<" "<<m[i]<<" "<<m[j]<<endl;
	// cout<<i<<" "<<j<<" "<<A<<" "<<B<<" "<<pnt<<endl;
	return max(pnt, 1LL);
	// return max(A - A + 1 , pnt);
}

long long take_photos(int n, int am, int k, vector<int> x, vector<int> y){
	vector<pair<ll, ll>> vc;
	for (ll i=0;i<n;i++){
		if (x[i] > y[i])
			swap(x[i], y[i]);
		vc.push_back({x[i] + 1, y[i] + 1});
	}

	n = 0;
	for (ll i=0, mxC = 0;i<vc.size();i++){
		if (vc[i].second <= mxC)
			continue;

		while (r[n] == vc[i].first)
			n--;
		n++;
		mxC = max(mxC, vc[i].second);
		r[n] = vc[i].first, c[n] = vc[i].second;
	}
	r[n+1] = r[n] + 1;

	for (ll i=0;i<=n;i++){
		m[i] = -2 * r[i + 1];
		for (ll j=0;j<2;j++)
			dp[i][j] = 1e16 * (i + j != 0);
	}

	ll Ans = 1LL * am * am;
	for (ll j=1;j<=k;j++){
		vector<ll> v = {0}, st = {0};

		for (ll i=1;i<=n;i++){
			ll L = 0, R = v.size();
			while (L + 1 < R){
				ll mid = (L + R) / 2;
				if (st[mid] > c[i])
					R = mid;
				else
					L = mid;
			}

			// ll lst = v[L];
			for (int lst=0;lst<i;lst++)
				dp[i][1] = min(dp[i][1], dp[lst][0] + (c[i] - r[lst] + 1) * (c[i] - r[lst] + 1));
			if (i + 1 <= n and c[i] >= r[i + 1])
				dp[i][1] -= (c[i] - r[i+1] + 1) * (c[i] - r[i+1] + 1);

			b[i] = dp[i][0] + r[i + 1] * (r[i + 1] - 2) + 1;

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

			st.push_back(intersection(v.back(), i));
			v.push_back(i);
		}
		Ans = min(Ans, dp[n][1]);
		for (int i=0;i<=n;i++)
			dp[i][0] = dp[i][1], dp[i][1] = 1e16;
	}
	return Ans;
}

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: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40