Submission #401846

#	Time	Username	Problem	Language	Result	Execution time	Memory
401846		peuch	Aliens (IOI16_aliens)	C++17	25 / 100	2095 ms	62092 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 lAux[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;
	}
};

vector<interval> ord;

void dat(int ini, int fim, int optMin, int optMax, int j){
	if(ini > fim) return;
	int mid = (ini + fim) >> 1;
	long long fmin = INF, id = 0;
	for(int i = optMin; i <= min(fim, optMax); i++){
		int h = lAux[i][mid];
		long long quad = (long long) (ord[mid].r - ord[i].l + 1) * (ord[mid].r - ord[i].l + 1);
		long long minus = ((h < 0 || ord[h].r < ord[i].l) ? 0 : ((long long) (ord[h].r - ord[i].l + 1) * (ord[h].r - ord[i].l + 1)));
		long long aux = quad + ((h < 0) ? 0 : dp[h][j - 1] - minus);
		if(aux < fmin) fmin = aux, id = i;
	}
	dp[mid][j] = fmin;
	dat(ini, mid - 1, optMin, id, j);
	dat(mid + 1, fim, id, optMax, j);
}

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

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

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:82:6: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   82 |      for(int j = 0; j <= i; j++)
      |      ^~~
aliens.cpp:84:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   84 |   update(1, 0, m, ord[i].l + 1, m, i);
      |   ^~~~~~

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