Submission #732431

#	Time	Username	Problem	Language	Result	Execution time	Memory
732431		sentheta	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	468 KiB

aliens

#include "aliens.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;

const int N = 505;
const int K = 505;
const int M = 1e6+5;

int n, m, k;

Int dp[N][K];
inline Int sqr(Int x){return x*x;}
const Int INF = 1e18;

Int solve(V<int> l,V<int> r){
	int sz = l.size();

	// dp[0][p]
	rep(p,1,k+1) dp[0][p] = sqr(r[0]-l[0]+1);
	// dp[1][0]
	rep(i,0,sz) dp[i][0] = INF;

	rep(i,1,sz) rep(p,1,k+1){
		// merge all
		dp[i][p] = sqr(r[i]-l[0]+1);

		// merge j until i
		for(int j=1; j<=i; j++){
			dp[i][p] = min({
				dp[i][p],
				dp[j-1][p-1] + sqr(r[i]-l[j]+1) - sqr(r[j-1]-l[j]+1)
			});
		}
	}

	return dp[sz-1][k];
}

Int take_photos(int _n,int _m,int _k,V<int> l,V<int> r){
	n = _n; m = _m; k = _k;

	// remove subsegments
	V<int> ord;
	rep(i,0,n){
		if(l[i] > r[i]) swap(l[i], r[i]);
		ord.push_back(i);
	}
	sort(all(ord),[&](int i,int j){
		if(l[i]==l[j]) return r[i] < r[j];
		return l[i] > l[j];
	});
	V<int> stak;
	for(int i : ord){
		while(!stak.empty() && r[stak.back()]<=r[i]) stak.pop_back();
		stak.push_back(i);
	}
	reverse(all(stak));
	ord.swap(stak);
	// result is ordered from l

	Int ans = 0;

	// solve for each group of connected segments
	int ordsz = ord.size();
	for(int i=0; i<ordsz;){
		int j = i, mxr = r[ord[i]];
		V<int> vl = {l[ord[i]]}, vr = {r[ord[i]]};
		while(j+1<ordsz && l[ord[j+1]]<=mxr){
			j++;
			vl.push_back(l[ord[j]]);
			vr.push_back(r[ord[j]]);
			mxr = max(mxr, r[ord[j]]);
		}

		ans += solve(vl, vr);

		i = j+1;
	}

	return ans;
}

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