oj.uz

Submission #49315

# Submission time Handle Problem Language Result Execution time Memory
49315 2018-05-25T15:20:42 Z IvanC Cover (COCI18_cover) C++17
12 / 120
 8 ms 928 KB 
#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.0 / 120.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 248 KB Output isn't correct
2 Correct 2 ms 512 KB Output is correct
3 Incorrect 2 ms 588 KB Output isn't correct
4 Incorrect 2 ms 588 KB Output isn't correct
5 Incorrect 2 ms 588 KB Output isn't correct
6 Incorrect 2 ms 632 KB Output isn't correct
7 Incorrect 3 ms 636 KB Output isn't correct
8 Incorrect 4 ms 644 KB Output isn't correct
9 Incorrect 7 ms 804 KB Output isn't correct
10 Incorrect 8 ms 928 KB Output isn't correct