제출 #98237

#제출 시각아이디문제언어결과실행 시간메모리
98237dalgerokCover (COCI18_cover)C++17
120 / 120
51 ms640 KiB
#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];
}
#Verdict Execution timeMemoryGrader output
Fetching results...