Submission #206578

#	Time	Username	Problem	Language	Result	Execution time	Memory
206578		TAISA_	Aliens (IOI16_aliens)	C++14	25 / 100	2054 ms	22392 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll INF=1LL<<60;
void chmin(ll &a,ll b){a=min(a,b);}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	vector<int> cs(m,-1);
	for(int i=0;i<n;i++){
		if(r[i]>c[i]){
			swap(r[i],c[i]);
		}
		cs[r[i]]=max(cs[r[i]],c[i]);
	}
	vector<ll> a,b;
	int ma=-1;
	for(int i=0;i<m;i++){
		if(cs[i]>ma){
			a.eb(i);
			b.eb(cs[i]);
			ma=cs[i];
		}
	}
	n=a.size();
	vector<vector<ll>> dp(k+1,vector<ll>(n+1,INF));
	dp[0][0]=0;
	for(int i=0;i<k;i++){
		for(int j=0;j<n;j++){
			for(int l=0;l<=j;l++){
				ll d=(b[j]-a[l]+1LL)*(b[j]-a[l]+1LL);
				if(l>0&&b[l-1]>=a[l]){
					d-=(b[l-1]-a[l]+1LL)*(b[l-1]-a[l]+1LL);
				}
				chmin(dp[i+1][j+1],dp[i][l]+d);
			}
			chmin(dp[i+1][j+1],dp[i][j+1]);
		}
	}
    return dp[k][n];
}

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