Submission #401796

#	Time	Username	Problem	Language	Result	Execution time	Memory
401796		peuch	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	296 KiB

aliens

#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 4e3 + 10;
const int MAXM = 1e6 + 10;
const long long INF = 1e18;

long long dp[MAXN][MAXN];
int seg[4 * MAXM];

struct interval{
	int l, r;
	interval(int _l = 0, int _r = 0){
		l = _l, r = _r;
		if(l > r) swap(l, r);
	}
	bool operator < (interval a){
		if(r == a.r) return l > a.l;
		return r < a.r;
	}
};

void update(int pos, int ini, int fim, int p, int q, int val){
	if(ini > q || fim < p) return;
	if(ini >= p && fim <= q){
		seg[pos] = max(seg[pos], val);
		return;
	}
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	update(e, ini, mid, p, q, val);
	update(d, mid + 1, fim, p, q, val);
}

int query(int pos, int ini, int fim, int id){
	if(ini > id || fim < id) return -1;
	if(ini == fim) return seg[pos];
	int mid = (ini + fim) >> 1, e = pos << 1, d = e | 1;
	return max(seg[pos], max(query(e, ini, mid, id), query(d, mid + 1, fim, id)));
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	vector<interval> ord (n);
	for(int i = 0; i < n; i++)
		ord[i] = interval(r[i], c[i]);
    sort(ord.begin(), ord.end());
    int minL = MAXM;
	for(int i = 0; i < n; i++){
    	minL = min(minL, ord[i].l);
		dp[i][0] = (long long)(ord[i].r - minL + 1) * (ord[i].r - minL + 1);
    }
    for(int j = 1; j < k; j++){
    	for(int i = 0; i < n; i++){
    		dp[i][j] = dp[i][j - 1];
    		for(int l = 0; l <= i; l++){
    			if(ord[l].l > ord[i].l) continue;
    			int h = query(1, 0, m, ord[l].l);
    			long long quad = (long long) (ord[i].r - ord[l].l + 1) * (ord[i].r - ord[l].l + 1);
    			long long minus = ((h < 0) ? 0 : ((long long) (ord[h].r - ord[l].l + 1) * (ord[h].r - ord[l].l + 1)));
    			long long aux = quad + ((h < 0) ? 0 : dp[h][j - 1] - minus);
				dp[i][j] = min(dp[i][j], aux);
				update(1, 0, m, ord[i].l + 1, ord[i].r, i);
			}
		}
	}
	return dp[n - 1][k - 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