Submission #171624

#	Time	Username	Problem	Language	Result	Execution time	Memory
171624		Sorting	Aliens (IOI16_aliens)	C++14	12 / 100	196 ms	4472 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 4007;
const long long inf = 1e18;

pair<int, int> p[MAXN];
long long dp[MAXN][MAXN];

void init_array(const int &n, const int &m, vector<int> &r, vector<int> &c){
	for(int i = 0; i < n; ++i){
		if(r[i] > c[i])
			swap(r[i], c[i]);

		p[i] = {r[i], c[i]};
	}
	sort(p, p + n);
}

long long do_dp(const int &n, const int &m, const int &k){
	for(int pos = 0; pos < n; ++pos)
		dp[0][pos] = inf;
	dp[0][n] = 0;

	for(int groups = 1; groups <= k; ++groups){
		for(int pos = 0; pos < n; ++pos){
			dp[groups][pos] = inf;

			long long mx = 0; 
			for(int next_pos = pos; next_pos < n; ++next_pos){
				mx = max(mx, (long long)p[next_pos].second  - p[pos].first + 1); 

				long long curr = mx * mx + dp[groups - 1][next_pos + 1];
				if(next_pos + 1 != n && p[next_pos + 1].first <= p[pos].first + mx - 1){
					if(p[next_pos + 1].second > p[pos].first + mx - 1)
						curr = inf;
					else{
						long long diff = p[pos].first + mx - p[next_pos + 1].first;
						curr -= diff * diff;
					}
				}

				dp[groups][pos] = min(dp[groups][pos], curr);
			}
		}
		dp[groups][n] = 0;
	}

	return dp[k][0];
}

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c){
	init_array(n, m, r, c);
  	return do_dp(n, m, k);
}

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