Submission #1104100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104100		alexander707070	Aliens (IOI16_aliens)	C++14	25 / 100	136 ms	4712 KiB

aliens

#include<bits/stdc++.h>

#define MAXN 1007
using namespace std;

const long long inf=1e17;

long long dp[MAXN][MAXN];

struct interval{
	int l,r;

	inline friend bool operator < (interval fr,interval sc){
		if(fr.l==sc.l)return fr.r>sc.r;
		return fr.l<sc.l;
	}
}s[MAXN],w[MAXN];

int n,m,k,sz;

long long area(long long l,long long r){
	if(l>r)return 0;

	return (r-l+1)*(r-l+1);
}

long long cost(int l,int r){
	return area(w[l].l,w[r].r) - area(w[l].l,w[l-1].r);
}

long long take_photos(int N, int M, int K, vector<int> r, vector<int> c){
	n=N; m=M; k=K;

	for(int i=1;i<=n;i++){
		s[i]={min(r[i-1],c[i-1])+1,max(r[i-1],c[i-1])+1};
	}

	sort(s+1,s+n+1);

	for(int i=1;i<=n;i++){
		if(sz>0 and s[i].r<=w[sz].r)continue;

		sz++; w[sz]=s[i];
	}

	for(int i=1;i<=sz;i++){
		dp[i][0]=inf;

		for(int f=1;f<=k;f++){
			dp[i][f]=inf;

			for(int t=i;t>=1;t--){
				dp[i][f]=min(dp[i][f],dp[t-1][f-1] + cost(t,i));
			}
		}
	}

	return dp[sz][k];
}

/*int main(){

	cout<<take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6})<<"\n";

	return 0;
}*/

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