Submission #290393

#	Time	Username	Problem	Language	Result	Execution time	Memory
290393		Saboon	Aliens (IOI16_aliens)	C++17	25 / 100	2090 ms	96376 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]);
}

vector<int> a;

pair<ll,ll> solve(ll x){
	int last = -1;
	for (int Iti = 0; Iti < a.size(); Iti++){
		int i = a[Iti];
		int Len = (i-get(0, i)+1);
		dp[i] = 1LL*(Len)*(Len)+x, pd[i] = 1, opt[i] = -1; 
		for (int Itj = 0; Itj < Iti; Itj++){
			int j = a[Itj];
			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;
		}
		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]);
		a.push_back(c[i]);
	}
	sort(a.begin(), a.end());
	a.resize(unique(a.begin(),a.end())-a.begin());
	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;
}

Compilation message (stderr)

aliens.cpp: In function 'std::pair<long long int, long long int> solve(ll)':
aliens.cpp:21:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int Iti = 0; Iti < a.size(); Iti++){
      |                    ~~~~^~~~~~~~~~
aliens.cpp:20:6: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   20 |  int last = -1;
      |      ^~~~

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