# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
639680 | classic | Cover (COCI18_cover) | C++14 | 77 ms | 408 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<pair<int, int>> pa;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
pa.emplace_back(abs(x), abs(y));
}
vector<pair<int, int>> pb;
for (int i = 0; i < n; i++) {
bool ok = true;
for (int j = 0; j < n; j++) {
if (pa[j].first > pa[i].first && pa[j].second > pa[i].second) {
ok = false;
}
}
if (ok) {
pb.emplace_back(pa[i]);
}
}
sort(pb.begin(), pb.end());
int m = pb.size();
vector<long long> dp(m + 1, 1e18);
dp[0] = 0;
for (int i = 0; i < m; i++) {
int mxy = 0;
for (int j = i; j >= 0; j--) {
mxy = max(mxy, pb[j].second);
dp[i + 1] = min(dp[i + 1], dp[j] + 1LL * pb[i].first * mxy);
}
}
cout << dp[m] * 4;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |