Submission #1032495

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032495		nishkarsh	Aliens (IOI16_aliens)	C++14	60 / 100	2096 ms	705488 KiB

aliens

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define vt vector
#define pb push_back

const int INF = 2e9;
const ll INFLL = 4e18;
const int N = 1e5+1;
const int mod = 998244353;

struct point{
	int x,y;

	point() {}
	
	point(int _x, int _y) : x(_x), y(_y) {}
	
	int64_t square_size(){
		int64_t ans = max(y+1-x,0);
		return ans*ans;
	}
};

point unite(const point a, const point b){
	int nwx = min(a.x,b.x);
	int nwy = max(a.y,b.y);
	return point(nwx,nwy);
}

point intersection(const point a, const point b){
	int nwx = max(a.x,b.x);
	int nwy = min(a.y,b.y);
	return point(nwx,nwy);
}

bool cmp(point a, point b){
	if(a.x == b.x) return a.y > b.y;
	else return a.x < b.x;
}

void dnc(vector<vector<pair<int64_t,point>>> &dp, int k, vector<point> &p, int lt_l, int lt_r, int rt_l, int rt_r){
	if(rt_r < rt_l) return;
	int rt_mid = (rt_l + rt_r) / 2;
	int lt_mid = lt_l;
	for(int i = lt_l; i <= lt_r && i <= rt_mid; i++){
		point curr_pt = unite(p[rt_mid],p[i]);
		int64_t curr = curr_pt.square_size();
		if(i) curr += dp[i-1][k-1].first - intersection(dp[i-1][k-1].second, curr_pt).square_size();
		if(curr <= dp[rt_mid][k].first){
			dp[rt_mid][k] = make_pair(curr,curr_pt);
			lt_mid = i;
		}
	}

	dnc(dp, k, p, lt_l, lt_mid, rt_l, rt_mid - 1);
	dnc(dp, k, p, lt_mid, lt_r, rt_mid + 1, rt_r);
}

int64_t take_photos(int n, int m, int k, vector<int> r, vector<int> c){
	point temp[n];
	for(int i = 0; i < n; i++){
		if(r[i] <= c[i]) temp[i] = point(r[i],c[i]);
		else temp[i] = point(c[i],r[i]);
	}
	sort(temp,temp+n,cmp);

	vector<point> p;

	int threshold = -1;
	for(int i = 0; i < n; i++){
		if(temp[i].y > threshold){
			// cout << temp[i].x << " " << temp[i].y << "\n";
			p.pb(temp[i]);
			threshold = temp[i].y;
		}
	}
	n = p.size();
	vector<vector<pair<int64_t,point>>> dp(n, vector<pair<int64_t,point>>(k,make_pair(int64_t(INFLL), point(-1,-1))));
	for(int i = 0; i < n; i++) dp[i][0] = make_pair(unite(p[i],p[0]).square_size(), unite(p[i],p[0]));
	for(int j = 1; j < k; j++) dnc(dp, j, p, 0, n-1, 0, n-1);

	// for(int i = 0; i < k; i++){
	// 	for(int j = 0; j < n; j++){
	// 		cout << dp[j][i] << " ";
	// 	}
	// 	cout << "\n";
	// }
	return dp[n-1][k-1].first;
}

void solve(){
	int n,m,k;
	cin >> n >> m >> k;
	vector<int> r(n),c(n);
	for(int i = 0; i < n; i++) cin >> r[i];
	for(int i = 0; i < n; i++) cin >> c[i];
	cout << take_photos(n,m,k,r,c) << "\n";
}

// int main() {

// 	ios_base::sync_with_stdio(false);
// 	cin.tie(0);
// 	cout.tie(0);

// 	int t = 1;
// 	// cin >> t;

// 	while(t--) solve();
// }

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