Submission #82095

#	Time	Username	Problem	Language	Result	Execution time	Memory
82095		Batrr	Aliens (IOI16_aliens)	C++14	0 / 100	3 ms	1004 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 = 0; 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);
    for(int i = 0; i < n; i++){
    	dp[i] = sqr(arr[i].s - arr[0].f + 1);
    	//cerr << i << " " << arr[i].f << " " << arr[i].s << " " << dp[i] << endl;
    	for(int j = 0; j < i; j++){
    		//cerr << sqr(arr[i].s - arr[j + 1].f + 1) << " " << sqr(max(0, arr[j].s - arr[j + 1].f + 1)) << endl; 
    		ll cur = dp[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;
    	}
    }
    return dp[n - 1];
}

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