Submission #239043

#	Time	Username	Problem	Language	Result	Execution time	Memory
239043		NONAME	Cover (COCI18_cover)	C++17	0 / 120	6 ms	512 KiB

cover

#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[n - 1]);

    for (int i = n - 2; i >= 0; --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: 0 / 120