Submission #569844

#	Time	Username	Problem	Language	Result	Execution time	Memory
569844		CSQ31	Aliens (IOI16_aliens)	C++17	12 / 100	98 ms	4616 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
vector<ll>dp[100001];
const ll INF = 1e18;
long long take_photos(int m, int n, int k, vector<int> r, vector<int> c) {
    vector<int>h(n,2*n);
    for(int i=0;i<m;i++){
		int a = max(r[i],c[i]);
		int b = min(r[i],c[i]);
		h[a] = min(h[a],b);
	}
	vector<int>b = {0};
	for(int i=0;i<n;i++){
		if(h[i]!=2*n)b.push_back(i);
	}
	n = b.size()-1;
	for(int i=0;i<=n;i++){
		dp[i].assign(k+1,INF);
	}
	dp[0][0] = 0;
	for(int i=1;i<=n;i++){
		int mn = h[b[i]];
		for(int j=i-1;j>=0;j--){
			for(int l=1;l<=k;l++){
				if(dp[j][l-1] != INF){
					ll len = b[i] - mn+1;
					len*=len;
					dp[i][l] = min(dp[i][l],dp[j][l-1] + len);
				}
			}
			mn = min(mn,h[b[j]]);
			
		}
	}
	ll ans = INF;
	for(int i=1;i<=k;i++)ans = min(ans,dp[n][i]);
	return ans;
}

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