Submission #49757

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49757	2018-06-02T18:41:17 Z	IvanC	Cover (COCI18_cover)	C++17	120 / 120	9 ms	912 KB

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.0 / 120.0

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