Submission #282685

#	Time	Username	Problem	Language	Result	Execution time	Memory
282685		theStaticMind	Aliens (IOI16_aliens)	C++14	60 / 100	2079 ms	9708 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"

int64_t dp[2][1000005];
vector<int> L(1000005);
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 && i <= mid; i++){
		if(dp[k][mid] > dp[k - 1][i] + cost(L[i], item[mid].second) - cost(L[i], item[i].second)){
			opt = i;
			dp[k][mid] = dp[k - 1][i] + cost(L[i], item[mid].second) - cost(L[i], item[i].second);
		}
	}

	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) {
	item.pb({0, 0});
	for(int i = 0; i < m; i++) item.pb({min(r[i], c[i])+1, max(r[i], c[i])+1});
	m++;

	sort(all(item), [&](ii a, ii b){return a.second < b.second;});

	for(int i = 0; i <= m; i++) dp[0][i] = dp[1][i] = 1e18;

	dp[0][0] = 0;

	
	L[m - 1] = n + 1;
	for(int r = m - 2; r >= 0; r--){
		L[r] = min(L[r + 1], item[r + 1].first);
	}


	for(int i = 1; i <= k; i++){
		dnc(1, 0, m - 1, 0, m - 1);
		for(int r = 0; r < m; r++) dp[1][r] = min(dp[1][r], dp[0][r]);
		for(int r = 0; r < m; r++){
			swap(dp[0][r], dp[1][r]);
			dp[1][r] = 1e18;
		}
	}

	return dp[0][m - 1];
}

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