Submission #295134

#	Time	Username	Problem	Language	Result	Execution time	Memory
295134		Plurm	Aliens (IOI16_aliens)	C++11	41 / 100	2076 ms	62976 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;

long long* dp[4005];
int n;
vector<pair<int,int> > its;
void computeDP(int lv, int l, int r, int ll = 0, int rr = n){
	if(l > r) return;
	int m = (l+r)/2;
	int midx = -1;
	long long mn = 1e18;
	for(int bck = ll; bck <= min(m-1, rr); bck++){
		int sl = its[m].second - its[bck+1].first + 1;
		int il = max(its[bck].second - its[bck+1].first + 1, 0);
		long long cval = dp[lv-1][bck] + 1ll * sl * sl - 1ll * il * il;
		if(cval < mn){
			mn = cval;
			midx = bck;
		}
	}
	dp[lv][m] = mn;
	computeDP(lv, l, m-1, ll, midx);
	computeDP(lv, m+1, r, midx, r);
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	::n = n;
	set<pair<int,int> > itvs;
	for(int i = 0; i < n; i++){
		if(c[i] < r[i]) swap(r[i], c[i]);
		auto it = itvs.lower_bound({r[i], 0});
		if(it != itvs.begin()){
			--it;
			if(it->second >= c[i]) continue; // this lies inside some intervals
			++it;
		}
		if(it != itvs.end() && it->first == r[i] && it->second >= c[i]) continue; // this lies inside some intervals
		while(it != itvs.end() && r[i] <= it->first && it->second <= c[i]){
			it = itvs.erase(it);
		}
		itvs.emplace(r[i], c[i]);
	}
	its = vector<pair<int,int> >(itvs.begin(), itvs.end());
	n = its.size();
	for(int i = 0; i <= k; i++){
		dp[i] = new long long[n+5];
		fill(dp[i], dp[i]+n+5, (long long)1e18);
	}
	its.insert(its.begin(), make_pair(-1,-1));
	long long ans = 1e18;
	dp[0][0] = 0ll;
	for(int j = 1; j <= k; j++){
		computeDP(j, 1, n);
		ans = min(ans, dp[j][n]);
	}
    return ans;
}

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