#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define ss(x) (int) x.size()
#define fi first
#define se second
#define cat(x) cerr << #x << " = " << x << endl
#define rep(i, j, n) for (int i = j; i <= n; ++i)
#define per(i, j, n) for (int i = n; j <= i; --i)
#define all(x) x.begin(), x.end()
using namespace std;
const int nax = 5005;
int n;
pair <int, int> t[nax];
ll dp[nax];
vector <pair<int, int>> v;
int main() {
scanf ("%d", &n);
rep(i, 0, n - 1) {
scanf ("%d%d", &t[i].fi, &t[i].se);
if (t[i].fi < 0) t[i].fi *= -1;
if (t[i].se < 0) t[i].se *= -1;
}
sort(t, t + n);
int a = -1e9;
per(i, 0, n - 1) {
if (t[i].se > a) v.pb(t[i]);
a = max(a, t[i].se);
}
v.pb({-1, -1});
reverse(all(v));
dp[0] = 0;
rep(i, 1, ss(v) - 1) {
dp[i] = 1e18;
rep(j, 0, i - 1) {
dp[i] = min(dp[i], dp[j] + (ll) v[i].fi * v[j + 1].se);
}
}
printf ("%lld\n", 4 * dp[ss(v) - 1]);
return 0;
}
Compilation message
cover.cpp: In function 'int main()':
cover.cpp:24:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &n);
~~~~~~^~~~~~~~~~
cover.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d%d", &t[i].fi, &t[i].se);
~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
256 KB |
Output is correct |
| 2 |
Correct |
4 ms |
256 KB |
Output is correct |
| 3 |
Correct |
6 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
256 KB |
Output is correct |
| 5 |
Correct |
4 ms |
256 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
5 ms |
384 KB |
Output is correct |
| 8 |
Correct |
5 ms |
384 KB |
Output is correct |
| 9 |
Correct |
7 ms |
384 KB |
Output is correct |
| 10 |
Correct |
8 ms |
512 KB |
Output is correct |
