Submission #140680

#	Time	Username	Problem	Language	Result	Execution time	Memory
140680		Sorting	Aliens (IOI16_aliens)	C++14	60 / 100	395 ms	44520 KiB

aliens

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

using namespace std;

const int N = 5e4 + 7;
const int K = 107;
const long long inf = 1e18;

bool cmp(pair<long long, long long> lvalue, pair<long long, long long> rvalue){
	if(lvalue.first != rvalue.first){
		return lvalue.first < rvalue.first;
	} 

	return lvalue.second > rvalue.second;
}

pair<long long, long long> p[N];
long long dp[N][K];

long long calc_dp(int pos, int left){
	if(pos < 0){
		return 0;
	}

	return dp[pos][left];
}

void solve(int l, int r, int l2, int r2, int k){
	if(l > r){
		return;
	}

	int mid = (l + r) >> 1, ptr = -1;

	dp[mid][k] = inf;
	for(int i = min(mid, r2); i >= max(0, l2); i--){
		long long curr = calc_dp(i - 1, k - 1);
		curr += (p[mid].second - p[i].first + 1ll) * (p[mid].second - p[i].first + 1ll);

		if(curr < dp[mid][k]){
			dp[mid][k] = curr;
			ptr = i;
		}
	}
	if(p[mid].second >= p[mid + 1].first){
		dp[mid][k] -= (p[mid].second - p[mid + 1].first + 1ll) * (p[mid].second - p[mid + 1].first + 1ll);
	}

	solve(l, mid - 1, l2, ptr, k);
	solve(mid + 1, r, ptr, r2, k);
}

long long take_photos(int n, int m, int k, 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].first = r[i];
    	p[i].second = c[i];
    }

    sort(p, p + n, cmp);

    int mx = -1, j = 0;

    for(int i = 0; i < n; i++){
    	if(p[i].second <= mx){
    		continue;
    	}
    	//cout << p[i].first << " p[i] " << p[i].second << endl;
    	mx = p[i].second;
    	p[j] = p[i];
    	j++;
    }
    n = j;
    p[n].first = inf;

    for(int i = 0; i < n; i++){
    	dp[i][0] = inf;
    }

    for(int i = 1; i <= k; i++){
    	solve(0, n - 1, 0, n - 1, i);
    }

    return dp[n - 1][k];
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
*/

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