Submission #98237

#	Time	Username	Problem	Language	Result	Execution time	Memory
98237		dalgerok	Cover (COCI18_cover)	C++17	120 / 120	51 ms	640 KiB

cover

#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 / 120