Submission #49757

#	Time	Username	Problem	Language	Result	Execution time	Memory
49757		IvanC	Cover (COCI18_cover)	C++17	120 / 120	9 ms	912 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(ll i = 1;i<N;i++){
		dp[i] = dp[i-1] + 1LL*pilha[i].first*pilha[i].second;
		for(ll j = i-1;j>=0;j--){
			ll custo = 1LL*pilha[i].first*pilha[j].second;
			if(j != 0) custo += dp[j-1];
			dp[i] = min(dp[i],custo);
		}
	}
	cout << dp[N-1]*4 << endl;
	return 0;
}

• Subtask 1: 120 / 120