oj.uz

Submission #239043

# Submission time Handle Problem Language Result Execution time Memory
239043 2020-06-14T08:03:23 Z NONAME Cover (COCI18_cover) C++17
0 / 120
 6 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[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.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 384 KB Output isn't correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Incorrect 4 ms 384 KB Output isn't correct
4 Incorrect 5 ms 368 KB Output isn't correct
5 Incorrect 4 ms 384 KB Output isn't correct
6 Incorrect 5 ms 384 KB Output isn't correct
7 Incorrect 5 ms 384 KB Output isn't correct
8 Incorrect 5 ms 384 KB Output isn't correct
9 Incorrect 5 ms 512 KB Output isn't correct
10 Incorrect 6 ms 512 KB Output isn't correct