oj.uz

Submission #98237

# Submission time Handle Problem Language Result Execution time Memory
98237 2019-02-21T16:06:37 Z dalgerok Cover (COCI18_cover) C++17
120 / 120
 51 ms 640 KB 
#include<bits/stdc++.h>
using namespace std;


const int N = 5005;



int n, x, y;
long long dp[N];
set < pair < int, int > > q;
vector < pair < int, int > > nq;


int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x >> y;
        q.insert(make_pair(abs(x), abs(y)));
    }
    nq.push_back(make_pair(-1, -1));
    while(!q.empty()){
        auto mn = *q.begin();
        q.erase(q.begin());
        bool p = true;
        for(auto it : q){
            if(it.first >= mn.first && it.second >= mn.second){
                p = false;
                break;
            }
        }
        if(p){
            nq.push_back(mn);
        }
    }
    n = (int)nq.size() - 1;
    for(int i = 1; i <= n; i++){
        dp[i] = 9e18;
        for(int j = 1; j <= i; j++){
            dp[i] = min(dp[i], dp[j - 1] + 4LL * nq[j].second * nq[i].first);
        }
    }
    cout << dp[n];
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 19 ms 512 KB Output is correct
10 Correct 51 ms 640 KB Output is correct