Submission #69503

#	Time	Username	Problem	Language	Result	Execution time	Memory
69503		leejseo	Aliens (IOI16_aliens)	C++11	25 / 100	60 ms	5612 KiB

aliens

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

typedef long long lld;

typedef struct point{
	lld r, c;
	point(lld r_, lld c_){
		r = min(r_, c_);
		c = max(r_, c_);
	}
	bool operator < (const point &other) const{
		return c != other.c ? c < other.c : r > other.r;
	}
} point;

vector<point> P, A;
int N = 0;
lld D[501][501];
const lld INF = 1LL<<62;
inline lld square (lld x) { return x * x; }

lld take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	for (int i=0; i<n; i++) P.push_back(point(r[i], c[i]));
	sort(P.begin(), P.end());
	for (int i=0; i<n; i++){
		point p = P[i];
		while (N){
			if ((A.back()).r >= p.r){
				--N;
				A.pop_back();
			}
			else break;
		}
		A.push_back(p);
		++N;
	}
	n = N;
	k = min(k, n);
	for (int i=0; i<n; i++){
		for (int j=2; j<=k; j++) D[i][j] = INF;
	}
	for (int i=0; i<n; i++) D[i][1] = square(A[i].c - A[0].r + 1);
	for (int l=1; l<k; l++){
		for (int i=l-1; i<n-1; i++){
			for (int j=i+1; j<n; j++){
				lld val = D[i][l] + square(A[j].c - A[i+1].r + 1);
				if (A[i+1].r <= A[i].c)
					val -= square(A[i].c - A[i+1].r + 1);
				D[j][l+1] = min(D[j][l+1], val);			
			}
		}
	}
	return D[n-1][k];
}

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