Submission #290381

#	Time	Username	Problem	Language	Result	Execution time	Memory
290381		Saboon	Aliens (IOI16_aliens)	C++17	4 / 100	505 ms	82680 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5, maxm = 1e6 + 5;
int n, m, k;
int Cmq[maxm][20], a[maxm];

ll dp[maxm], pd[maxm];

int get(int l, int r){
	int len = (r-l+1);
	len = log2(len);
//	cout << "Cmq " << l << " " << r << " : " << len << " : " << min(Cmq[l][len], Cmq[r-(1<<len)+1][len]) << endl;
	return min(Cmq[l][len], Cmq[r-(1<<len)+1][len]);
}

pair<ll,ll> solve(ll x){
	for (int i = 0; i < m; i++){
		if (get(i,i) >= m)
			continue;
		int Len = (i-get(0, i)+1);
		dp[i] = 1LL*(Len)*(Len)+x, pd[i] = 1; 
		for (int j = 0; j < i; j++){
			int minLen = get(j+1,i);
			int myLen = get(j,j);
			if (myLen > minLen)
				continue;
//			cout << j+1 << " " << i << " : " << minLen << endl;
			ll Q = (i-minLen+1);
			ll P = max(0,(j-minLen+1));
			ll now = dp[j] + 1LL*Q*Q - 1LL*P*P + x;
//			cout << j << " " << now << " " << Q << " " << P << " -> " << i << endl;
			if (make_pair(now,pd[j]+1) <= make_pair(dp[i],pd[i]))
				dp[i] = now, pd[i] = pd[j]+1;
		}
//		cout << i << " : " << dp[i] << " " << pd[i] << endl;
	}
	for (int i = m-1; i >= 1; i--)
		if (get(i,i) < m)
			return {dp[i],pd[i]};
	return {dp[0],pd[0]};
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
    memset(Cmq, 63, sizeof Cmq);
	::n = n, ::m = m, ::k = k;
	for (int i = 0; i < n; i++)
		if (r[i] > c[i])
			swap(r[i],c[i]);
	for (int i = 0; i < n; i++)
		Cmq[c[i]][0] = min(Cmq[c[i]][0], r[i]);
	for (int i = 1; i < 20; i++)
		for (int j = 0; j+(1<<(i-1)) < m; j++)
			Cmq[j][i] = min(Cmq[j][i-1], Cmq[j+(1<<(i-1))][i-1]);
	memset(a, 63, sizeof a);
	for (int i = 0; i < n; i++)
		a[max(r[i],c[i])] = min(a[max(r[i],c[i])], min(r[i],c[i]));
	ll lo = 0, hi = 1e12 + 1;
	solve(1);
	while (hi-lo > 1){
		ll mid = (lo+hi) >> 1;
		if (solve(mid).second > k)
			lo = mid;
		else
			hi = mid;
	}
	auto it = solve(hi);
	return it.first - hi*it.second;
}

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