Submission #290390

#	Time	Username	Problem	Language	Result	Execution time	Memory
290390		Saboon	Aliens (IOI16_aliens)	C++17	12 / 100	509 ms	159096 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];

ll dp[maxm], pd[maxm], opt[maxm];

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

pair<ll,ll> solve(ll x){
	int last = -1;
	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, opt[i] = -1; 
		for (int j = 0; j < i; j++){
			int minLen = get(j+1,i);
			int myLen = get(j,j);
			if (myLen > minLen)
				continue;
			ll Q = (i-minLen+1);
			ll P = max(0,(j-minLen+1));
			ll now = dp[j] + 1LL*Q*Q - 1LL*P*P + x;
			if (make_pair(now,pd[j]+1) <= make_pair(dp[i],pd[i]))
				dp[i] = now, pd[i] = pd[j]+1, opt[i] = j;
		}
		assert(opt[i] >= last);
		last = opt[i];
	}
	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]);
	ll lo = -1, hi = 1e12 + 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*k;
}

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