Submission #786852

#	Time	Username	Problem	Language	Result	Execution time	Memory
786852		LuoBo	Aliens (IOI16_aliens)	C++14	25 / 100	130 ms	4360 KiB

aliens

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

const int MAXN=10010;
struct node {
	int x, y;
} t[MAXN], p[MAXN];
long long f[MAXN][MAXN];

bool cmp(node x, node y) { return x.x==y.x ? x.y<y.y : x.x<y.x ; }
long long sq(long long x) { return x*x; }

long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
	
	for (int i=0; i<n; i++) {
		t[i].x=r[i]; t[i].y=c[i];
		if ( r[i]>c[i] ) swap(t[i].x,t[i].y); 
	}
	sort(t, t+n, cmp);
	
	int right=-1, tt=0;
	p[0].x=-1; p[0].y=-1;
	for (int i=0; i<n; i++) {
		if ( t[i].y<=right ) continue;
		right=t[i].y; p[++tt]=t[i];
	}
	n=tt;
	
//	for (int i=0;i<n;i++) printf("%d %d\n",p[i].x,p[i].y);
	
	long long ans=1e10;
	for (int i=0;i<=n;i++)
		for (int opt=0;opt<=k;opt++) f[i][opt]=1e15;
	f[0][0]=0;
	
	for (int i=1; i<=n; i++) {
		for (int opt=1; opt<=k; opt++) {
			for (int j=0; j<i; j++) {
				f[i][opt]=min(f[i][opt], f[j][opt-1] + sq( p[i].y-p[j+1].x+1 ) - sq( max(0, p[j].y-p[j+1].x+1) ) );
			}
		}
	}
	
	for (int opt=1;opt<=k;opt++) ans=min(ans,f[n][opt]);
	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