Submission #49315

#	Time	Username	Problem	Language	Result	Execution time	Memory
49315		IvanC	Cover (COCI18_cover)	C++17	12 / 120	8 ms	928 KiB

cover

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

typedef pair<int,int> ii;
typedef long long ll;

const int MAXN = 5010;

ll dp[MAXN],N;
vector<ii> ordenado,pilha;

int main(){
	cin >> N;
	for(int i = 1;i<=N;i++){
		int a,b;
		cin >> a >> b;
		ordenado.push_back(ii(abs(a),abs(b)));
	}
	sort(ordenado.begin(),ordenado.end());
	for(ii par : ordenado){
		while(!pilha.empty() && pilha.back().second <= par.second) pilha.pop_back();
		pilha.push_back(par);
	}
	N = pilha.size();
	dp[0] = 1LL*pilha[0].first*pilha[0].second;
	for(int i = 1;i<N;i++){
		dp[i] = 1e18;
		for(ll j = i-1;j>=0;j--){
			dp[i] = min(dp[i], dp[j] + 1LL*pilha[i].first*pilha[j+1].second );
		}
	}
	cout << dp[N-1]*4 << endl;
	return 0;
}

• Subtask 1: 12 / 120