제출 #501977

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501977		blue	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	248 ms	12976 KiB

bridge

#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
#define sz(x) int(x.size())
const ll INF = 1'000'000'000'000'000'000LL;





multiset<ll> lo, hi;
ll lo_sum, hi_sum;

void insert_pair(ll u, ll v)
{
    if(max(u, *lo.rbegin()) <= min(v, *hi.begin()))
    {
        lo.insert(u);
        lo_sum += u;

        hi.insert(v);
        hi_sum += v;
    }
    else if(max(*lo.rbegin(), v) <= *hi.begin())
    {
        lo.insert(u);
        lo.insert(v);
        lo_sum += u+v;

        lo_sum -= *lo.rbegin();
        hi_sum += *lo.rbegin();

        hi.insert(*lo.rbegin());
        lo.erase(lo.find(*lo.rbegin()));
    }
    else
    {
        hi.insert(u);
        hi.insert(v);
        hi_sum += u+v;

        hi_sum -= *hi.begin();
        lo_sum += *hi.begin();

        lo.insert(*hi.begin());
        hi.erase(hi.begin());
    }
}



void solve_2()
{
    int N;
    cin >> N;

    ll basicCost = 0;

    // vll points;

    vector<pll> points;

    for(int i = 1; i <= N; i++)
    {
        char Z1, Z2;
        ll P1, P2;
        cin >> Z1 >> P1 >> Z2 >> P2;

        if(Z1 == Z2)
        {
            basicCost += abs(P1 - P2);
        }
        else
        {
            basicCost += 1;
            // points.push_back(P1);
            // points.push_back(P2);
            points.push_back({min(P1, P2), max(P1, P2)});
        }
    }

    sort(points.begin(), points.end(), [] (pll a, pll b)
    {
        return a.first + a.second < b.first + b.second;
    });

    int S = sz(points);

    if(S == 0)
    {
        cout << basicCost << '\n';
        return;
    }



    vll left_cost(1+S);
    left_cost[0] = 0;

    lo.insert(points[0].first);
    lo_sum = points[0].first;

    hi.insert(points[0].second);
    hi_sum = points[0].second;

    left_cost[1] = hi_sum - lo_sum;

    for(int i = 2; i <= S; i++)
    {
        // ll u = points[i-1].first, v = points[i-1].second;
        insert_pair(points[i-1].first, points[i-1].second);

        left_cost[i] = hi_sum - lo_sum;
    }






    lo.clear();
    hi.clear();
    lo_sum = 0;
    hi_sum = 0;

    vll right_cost(1+S);
    right_cost[S] = 0;

    lo.insert(points[S-1].first);
    lo_sum += points[S-1].first;

    hi.insert(points[S-1].second);
    hi_sum += points[S-1].second;

    right_cost[S-1] = hi_sum - lo_sum;

    for(int i = S-2; i >= 0; i--)
    {
        insert_pair(points[i].first, points[i].second);
        right_cost[i] = hi_sum - lo_sum;
    }

    ll ans = INF;
    for(int i = 0; i <= S; i++) ans = min(ans, left_cost[i] + right_cost[i]);

    ans += basicCost;

    cout << ans << '\n';
}

void solve_1()
{
    int N;
    cin >> N;

    ll basicCost = 0;

    vll points;

    for(int i = 1; i <= N; i++)
    {
        char Z1, Z2;
        ll P1, P2;
        cin >> Z1 >> P1 >> Z2 >> P2;

        if(Z1 == Z2)
        {
            basicCost += abs(P1 - P2);
        }
        else
        {
            basicCost += 1;
            points.push_back(P1);
            points.push_back(P2);
        }
    }

    sort(points.begin(), points.end());

    ll ans = 0;
    for(int i = 0; i < sz(points)/2; i++)
        ans -= points[i];
    for(int i = sz(points)/2; i < sz(points); i++)
        ans += points[i];

    cout << ans + basicCost << '\n';
}

int main()
{
    int K;
    cin >> K;

    if(K == 1) solve_1();
    else solve_2();
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 37 / 37