Submission #206582

#	Time	Username	Problem	Language	Result	Execution time	Memory
206582		TAISA_	Aliens (IOI16_aliens)	C++14	25 / 100	2085 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-1);
			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++){
		vector<ll> t(n+1);
		for(int j=0;j<n;j++){
			t[j]=dp[i][j]+a[j]*a[j];
			if(j>0&&b[j-1]>=a[j]+1){
				t[j]-=(b[j-1]-a[j])*(b[j-1]-a[j]);
			}
		}
		for(int j=0;j<n;j++){
			for(int l=0;l<=j;l++){
				chmin(dp[i+1][j+1],-2LL*a[l]*b[j]+t[l]+b[j]*b[j]);
			}
			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