제출 #104945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
104945		fbosnjak	Cover (COCI18_cover)	C++14	12 / 120	95 ms	640 KiB

cover

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define dd double

const int maxn = 5050;
const ll maxdp = 1e18;
const ll maxi = 1e9;
const pair <dd, dd> maxp = make_pair((dd)maxi, (dd)maxi);
int N;
ll X, Y;
vector <pair <ll, ll> > v1, v;
ll dp[maxn]; // dp[i] = min(dp[j - 1] + Y[j] * X[i]);

// l1 - l2 / k2 - k1

vector <pair <ll, ll> > convex;
vector <pair <dd, dd> > intervali;

int bs(dd x)
{
    int pos = upper_bound(intervali.begin(), intervali.end(), make_pair(x, (dd)maxi)) - intervali.begin();
    pos--;
    return pos;
}

double sijeku(int x)
{
    int sz = convex.size();
    sz --;
    return (convex[sz].second - dp[x + 1]) / (v[x + 1].second - convex[sz].first);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> X >> Y;
        X = abs(X);
        Y = abs(Y);
        v1.push_back(make_pair(X, Y));
    }

    for (int i = 0; i < N; i++)
    {
        bool da = 1;
        for (int j = 0; j < N; j++)
        {
            if (v1[i].first < v1[j].first && v1[i].second <= v1[j].second) da = 0;
            if (v1[i].first <= v1[j].first && v1[i].second < v1[j].second) da = 0;
        }
        if (da) v.push_back(v1[i]);
    }

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for (int i = 1; i < maxn; i++) dp[i] = maxdp;

    convex.push_back(make_pair(v[0].second, 0));
    intervali.push_back(make_pair(0, maxi));
    intervali.push_back(maxp);

    for (int i = 0; i < (int)v.size(); i++)
    {
        int koji = bs((dd)(v[i].first));
        dp[i + 1] = convex[koji].second + convex[koji].first * v[i].first;
        if (i < (int)v.size() - 1)
        {
            bool brisi = 1;
            intervali.pop_back();
            dd poz = sijeku(i);
            while (brisi && (int)convex.size() >= 2)
            {
                if (poz <= intervali[intervali.size() - 1].first) {convex.pop_back(); intervali.pop_back();}
                else {intervali[intervali.size() - 1].second = poz; brisi = 0;}
            }
            convex.push_back(make_pair(v[i + 1].second, dp[i + 1]));
            intervali.push_back(make_pair(poz, maxi));
            intervali.push_back(maxp);
        }

        /*for (int j = 0; j < intervali.size() - 1; j++) cout << intervali[j].first << ' ' << intervali[j].second << " // ";
        cout << endl;*/
    }

    cout << dp[(int)v.size()] * 4 << endl;
}

• Subtask 1: 12 / 120