Submission #239841

#	Time	Username	Problem	Language	Result	Execution time	Memory
239841		MrRobot_28	Cover (COCI18_cover)	C++17	120 / 120	9 ms	512 KiB

cover

#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 / 120