Submission #1326623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326623		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 = 505;
ll dp[N][N], 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;
	}

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

	ll Ans = 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] > r[i])
					R = mid;
				else
					L = mid;
			}

			ll lst = v[L];
			// cout<<i<<"_"<<j<<"_"<<lst<<"_"<<dp[lst][j - 1]<<'_';
			dp[i][j] = dp[lst][j - 1] + (c[i] - r[lst + 1] + 1) * (c[i] - r[lst + 1] + 1);
			if (i + 1 <= n and c[i] >= r[i + 1])
				dp[i][j] -= (c[i] - r[i+1] + 1) * (c[i] - r[i+1] + 1);
			// cout<<lst<<',';

			// cout<<dp[i][j]<<' ';
			if (i == n)
				continue;

			b[i] = dp[i][j - 1] + 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);
			// cout<<st.back()<<'\n';
		}
		// cout<<'\n';
		Ans = min(Ans, dp[n][j]);
	}
	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