/*
This code belongs to Aadit Ambadkar
Date: 2022-02-08 17:19:16
Problem: cover
*/
#include <bits/stdc++.h>
using namespace::std;
typedef long long ll;
#define F0R(i, n) for (int i = 0; i < n; i++)
#define R0F(i, n) for (int i = n-1; i >= 0; i--)
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define pb push_back
#define fastio ios::sync_with_stdio(0); cin.tie(0)
#define MOD 1000000007
#define INF 2e18+10
#define FF first
#define SS second
int main() {
fastio;
int n; cin >> n;
int ne[n+1];
pair<ll, ll> pt[n+1];
ll dp[n+1];
memset(ne, 0, sizeof(ne));
memset(dp, 0, sizeof(dp));
FOR(i, 1, n+1) {
cin >> pt[i].FF >> pt[i].SS;
pt[i].FF = abs(pt[i].FF);
pt[i].SS = abs(pt[i].SS);
}
sort(pt+1, pt+n+1);
FOR(i, 1, n+1) {
ne[i]=0;
for (int j = i-1; j >= 1; j--) {
if (pt[j].SS > pt[i].SS) {
ne[i]=j;
break;
}
}
}
// cout << "c1" << endl;
FOR(i, 1, n+1) {
dp[i]=INF;
}
// cout << "c2" << endl;
// cout << n << endl;
FOR(i, 1, n+1) {
int at = i;
// cout << "p" << i << endl;
while (at != 0) {
// cout << i << " " << at << endl;
dp[i]=min(dp[i], 4LL*pt[i].FF*pt[at].SS+dp[ne[at]]);
at=ne[at];
}
// cout << "c" << i << endl;
}
// FOR(i, 1, n) {
// cout << dp[i] << " ";
// }
cout << dp[n] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
312 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
268 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
316 KB |
Output is correct |
| 8 |
Correct |
2 ms |
332 KB |
Output is correct |
| 9 |
Correct |
7 ms |
324 KB |
Output is correct |
| 10 |
Correct |
10 ms |
512 KB |
Output is correct |
