oj.uz

Submission #200151

# Submission time Handle Problem Language Result Execution time Memory
200151 2020-02-05T14:11:03 Z Saboon Cover (COCI18_cover) C++14
120 / 120
 9 ms 504 KB 
#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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 424 KB Output is correct
9 Correct 7 ms 376 KB Output is correct
10 Correct 9 ms 504 KB Output is correct