Submission #282412

#	Time	Username	Problem	Language	Result	Execution time	Memory
282412		theStaticMind	Aliens (IOI16_aliens)	C++14	25 / 100	40 ms	33268 KiB

aliens

#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
using namespace std;
#include "aliens.h"

vector<vector<int64_t> > dp;
vector<int> L(100005);
vector<ii> item;

int64_t cost(int64_t l, int64_t r){
	if(r < l) return 0;
	return (r - l + 1) * (r - l + 1);
}

void dnc(int k, int l, int r, int optl, int optr){
	if(r < l) return;

	int mid = (l + r) / 2;

	int opt = optl;

	for(int i = optl; i <= optr && L[i] < sz(item) && item[L[i]].second <= mid; i++){
		if(dp[k][mid] > dp[k - 1][i] + cost(item[L[i]].first, mid) - cost(item[L[i]].first, i)){
			opt = i;
			dp[k][mid] = dp[k - 1][i] + cost(item[L[i]].first, mid) - cost(item[L[i]].first, i);
		}
	}

	dnc(k, l, mid - 1, optl, opt);
	dnc(k, mid + 1, r, opt, optr);
}

long long take_photos(int m, int n, int k, std::vector<int> r, std::vector<int> c) {

	for(int i = 0; i < m; i++) item.pb({min(r[i], c[i])+1, max(r[i], c[i])+1});

	sort(all(item));

	dp = vector<vector<int64_t> > (2, vector<int64_t>(n + 1, INF));

	dp[0][0] = 0;

	int t = 0;
	for(int r = 0; r <= n; r++){
		while(t < m && item[t].second <= r) t++;
		L[r] = t;
	}


	for(int i = 1; i <= k; i++){
		dnc(1, 0, n, 0, n);
		for(int r = 0; r <= n; r++) dp[1][r] = min(dp[1][r], dp[0][r]);
		swap(dp[0], dp[1]);
		for(auto& p : dp[1]) p = INF;
	}

	int maxr = 0;
	for(int i = 0; i < m; i++){
		maxr = max(maxr, item[i].second);
	}

	return dp[0][maxr];
}

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