Submission #295055

#	Time	Username	Problem	Language	Result	Execution time	Memory
295055		Plurm	Aliens (IOI16_aliens)	C++11	12 / 100	145 ms	4388 KiB

aliens

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

long long dp[4005][4005];
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	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]);
	}
	vector<pair<int,int> > its(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++){
		dp[j][0] = 1e18;
		for(int i = 1; i <= n; i++){
			dp[j][i] = 1e18;
			for(int bck = 0; bck < i; bck++){
				int sl = its[i].second - its[bck+1].first + 1;
				int il = max(its[bck].second - its[bck+1].first, 0);
				dp[j][i] = min(dp[j][i], dp[j-1][bck] + 1ll * sl * sl - 1ll * il * il);
			}
		}
		ans = min(ans, dp[j][n]);
	}
    return ans;
}

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