oj.uz

Submission #239044

# Submission time Handle Problem Language Result Execution time Memory
239044 2020-06-14T08:04:45 Z NONAME Cover (COCI18_cover) C++17
120 / 120
 7 ms 512 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#include <algorithm>
using namespace std;

using ll = long long;

const int N = 2e5 + 10;
const ll oo = 1e18;

int n;
ll dp[int(1e5)];
vector <pair <ll, ll> > v, cur;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        ll x, y;
        cin >> x >> y;
        v.push_back(make_pair(abs(x), abs(y)));
    }

    sort(v.rbegin(), v.rend());
    cur.push_back(v[0]);

    for (int i = 0; i < n; ++i)
        if (v[i].second > cur.back().second)
            cur.push_back(v[i]);

    reverse(cur.begin(), cur.end());
    int m = cur.size();

//    cerr << "\n";
//
//    for (auto i : cur)
//        cerr << i.first << ' ' << i.second << "\n";

    for (int i = 0; i <= m; ++i)
        dp[i] = oo;
    dp[0] = 0;

    for (int i = 0; i < m; ++i)
    for (int j = i; j < m; ++j)
        dp[j + 1] = min(dp[j + 1], dp[i] + cur[i].second * cur[j].first);

    cout << dp[m] * 4;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 4 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 512 KB Output is correct
10 Correct 7 ms 512 KB Output is correct