Submission #200151

#	Time	Username	Problem	Language	Result	Execution time	Memory
200151		Saboon	Cover (COCI18_cover)	C++14	120 / 120	9 ms	504 KiB

cover

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 5000 + 37;

pair<int,int> p[maxn];
ll dp[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++){
		int x, y;
		cin >> x >> y;
		x = abs(x), y = abs(y);
		p[i] = {x,y};
	}
	sort(p, p + n);
	vector<int> a;
	for (int i = 0; i < n; i++){
		while (!a.empty() and p[a.back()].second <= p[i].second)
			a.pop_back();
		a.push_back(i);
	}
	n = a.size();
	memset(dp, 63, sizeof dp);
	dp[0] = 0;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= i; j++){
			int X = 2 * p[a[i - 1]].first, Y = 2 * p[a[j - 1]].second;
			dp[i] = min(dp[i], dp[j - 1] + 1ll * X * Y);
		}
	}
	cout << dp[n] << '\n';
}

• Subtask 1: 120 / 120