Submission #290418

#	Time	Username	Problem	Language	Result	Execution time	Memory
290418		Saboon	Aliens (IOI16_aliens)	C++17	41 / 100	2081 ms	3440 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;
const ll inf = 1e18;
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]);
}

vector<pair<int,int>> A;

pair<ll,ll> solve(ll x){
	int sz = A.size();
	for (int i = 0; i < sz; i++){
		dp[i] = inf;
		for (int j = 0; j <= i; j++){
			ll Q = A[i].second-A[j].first+1;
			ll Cost = Q*Q;
			ll Add = 0;
			ll cnt = 1;
			if (j != 0){
				cnt += pd[j-1];
				Add += dp[j-1];
				int r = A[j].first, c = A[j-1].second;
				ll P = max(0,(c-r+1));
				Add -= P*P;
			}
			if (make_pair(Cost+Add+x,cnt) < make_pair(dp[i],pd[i]))
				dp[i] = Cost+Add+x, pd[i] = cnt, opt[i] = j;
		}
	}
	for (int i = 0; i < sz-1; i++)
		assert(opt[i] <= opt[i+1]);
	return {dp[sz-1],pd[sz-1]};
}
 
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
	::n = n, ::m = m, ::k = k;
	for (int i = 0; i < n; i++)
		if (r[i] > c[i])
			swap(r[i],c[i]);
	vector<pair<int,int>> Tmp;
	for (int i = 0; i < n; i++)
		Tmp.push_back({r[i],c[i]});
	sort(Tmp.begin(),Tmp.end());
	for (int i = 0; i < n; i++){
		if (!A.empty() and A.back().first == Tmp[i].first){
			A.pop_back();
			A.push_back(Tmp[i]);
		}
		else if (A.empty() or A.back().second < Tmp[i].second)
			A.push_back(Tmp[i]);
	}
	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: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40