oj.uz

Submission #239841

# Submission time Handle Problem Language Result Execution time Memory
239841 2020-06-17T11:38:57 Z MrRobot_28 Cover (COCI18_cover) C++17
120 / 120
 9 ms 512 KB 
#include <bits/stdc++.h>
                  
using namespace std;
#define int long long
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	vector <pair <int, int> > x(n);
	for(int i = 0; i < n; i++)
	{
		cin >> x[i].first >> x[i].second;
		x[i].first = abs(x[i].first);
		x[i].second = abs(x[i].second);
	}
	sort(x.begin(), x.end());
	vector <pair <int, int> > new_x;
	for(int i = 0; i < n; i++)
	{
		while(new_x.size() > 0 && new_x.back().second <= x[i].second)
		{
			new_x.pop_back();
		}
		new_x.push_back(x[i]);
	}
	int m = new_x.size();
	vector <int> dp(m, 1e18);
	for(int i = 0; i < m; i++)
	{
		for(int j = 0; j <= i; j++)
		{
			if(j == 0)
			{
				dp[i] = new_x[j].second * new_x[i].first;
			}
			else
			{
				dp[i] = min(dp[i], dp[j - 1] + new_x[j].second * new_x[i].first);
			}
		}
	}
	cout << dp[m - 1] * 4;
	return 0;
}

Subtask #1
120.0 / 120.0

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