Created
March 7, 2018 21:08
-
-
Save fredbr/b6ce4c71837c611188ed7579729db9b1 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
#define ff first | |
#define ss second | |
using namespace std; | |
// o resultado pode ultrapassar o inteiro normal | |
typedef long long ll; | |
typedef pair<ll, ll> ii; | |
const int maxn = 5010; | |
ii v[maxn]; | |
ii d[maxn]; | |
ll dp[maxn]; | |
int main() | |
{ | |
ios_base::sync_with_stdio(false); | |
cin.tie(0); | |
int n; | |
cin >> n; | |
for (int i = 1; i <= n; i++) { | |
cin >> v[i].ff >> v[i].ss; | |
// tratamos somente com o primeiro quadrante | |
v[i].ff = abs(v[i].ff); | |
v[i].ss = abs(v[i].ss); | |
} | |
sort(v+1, v+n+1); | |
// ponteiro para o ultimo elemento processado | |
int cur = 0; | |
for (int i = 1; i <= n; i++) { | |
// remove o elemento anterior caso irrelevante | |
while (cur > 0 and v[i].ss >= d[cur].ss) cur--; | |
// coloca o elemento atual | |
d[++cur] = v[i]; | |
} | |
// lembrar de recontar o numero de elementos | |
n = cur; | |
// torna dp[i] infinito para todo i != 0 | |
memset(dp, 0x3f, maxn*8); | |
dp[0] = 0ll; | |
// loop que calcula a dp para todos os i | |
for (int i = 1; i <= n; i++) { | |
// loop para calcular o dp[i] | |
for (int j = 0; j < i; j++) { | |
dp[i] = min(dp[i], dp[j] + d[j+1].ss*d[i].ff); | |
} | |
} | |
cout << dp[n]*4ll << "\n"; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment