제출 #295128

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
295128		Plurm	Aliens (IOI16_aliens)	C++11	41 / 100	479 ms	72952 KiB

aliens

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

long long dp[4005][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();
	its.insert(its.begin(), make_pair(-1,-1));
	long long ans = 1e18;
	for(int i = 1; i <= n; i++) dp[0][i] = 1e18;
	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