Submission #82097

#	Time	Username	Problem	Language	Result	Execution time	Memory
82097		Batrr	Aliens (IOI16_aliens)	C++14	25 / 100	2068 ms	1464 KiB

aliens

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

#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 

using namespace std;                    

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = (int)1e5 + 123, inf = 1e9;
const ll INF = 1e18;

using namespace std;

ll sqr(ll x){
	return x * x;
}
ll take_photos(int n, int m, int k, vector<int> row, vector<int> col) {
	vector< pii > arr, arr2;
	
	for(int i = 0; i < n; i++){
		int l, r;
		l = row[i];
		r = col[i];
		if(l > r)
			swap(l, r);	
		arr2.pb({l, -r});
	}
	sort(arr2.begin(), arr2.end());
	for(int i = 0, mx = -1; i < n; i++){
		int l = arr2[i].f;
		int r = -arr2[i].s;
		if(r <= mx)
			continue;
		mx = r;
		arr.pb({l, r});
	}
	n = arr.size();
	vector< ll > dp(n, INF);
	vector< ll > last(n, INF);
	ll ans = INF;
	for(int q = 1; q <= k ; q++){
    	
    	for(int i = 0; i < n; i++){
    		dp[i] = sqr(arr[i].s - arr[0].f + 1);
    		for(int j = 0; j < i; j++){
    			ll cur = last[j] + sqr(arr[i].s - arr[j + 1].f + 1) - sqr(max(0, arr[j].s - arr[j + 1].f + 1));
    			if(cur < dp[i])
    				dp[i] = cur;
    		}
    	}

    	if(ans > dp[n - 1])
    		ans = dp[n - 1];
    	
    	for(int i = 0; i < n; i++)
    		last[i] = dp[i];

	}
    return ans;
}

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