제출 #1054428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1054428		unnick	Palembang Bridges (APIO15_bridge)	C++14	100 / 100	73 ms	4412 KiB

bridge

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long int ll;

int main() {
    int k, n;
    cin >> k >> n;
    if (k != 1) {
        
        vector<pair<int, int> > a;
        ll sum = 0;

        for (int i = 0; i < n; i++) {
            char sa, sb;
            int ia, ib;
            cin >> sa >> ia >> sb >> ib;
            if (sa == sb) {
                sum += abs(ia-ib);
                continue;
            }
            a.push_back(make_pair(ia, ib));
            sum += 1;
        }
        // if (a.size() == 1) {
        //     cout << sum + abs(a[0].first - a[0].second) << "\n";
        // }
        sort(a.begin(), a.end(), [](auto a, auto b){
            return a.first + a.second < b.first + b.second;
        });

        n = a.size();

        vector<ll> lh_s(n+1);
        vector<ll> hh_s(n+1);

        // for (auto b : a) {
        //     cout << b.first << " " << b.second << "\n";
        // }

        for (int q = 0; q < 2; q++) {
            // cout << "== " << q << "\n";
            if (q == 1) {
                for (int i = 0; i < a.size()/2; i++) {
                    auto tmp = a[i];
                    a[i] = a[a.size()-i-1];
                    a[a.size()-i-1] = tmp;
                }
            }
            ll ls = 0, hs = 0;
            priority_queue<int> lh;
            priority_queue<int, vector<int>, greater<int> > hh;

            bool fst = true;
            int ptr = q == 0 ? 0 : a.size();
            for (auto b : a) {
                // cout << "=" << ls << " " << hs << "\n";
                if (q == 0) lh_s[ptr++] = hs - ls; else hh_s[ptr--] = hs - ls;
                if (fst) {
                    lh.push(min(b.first, b.second));
                    hh.push(max(b.first, b.second));
                    ls = min(b.first, b.second);
                    hs = max(b.first, b.second);
                    fst = false;
                    continue;
                }
                if (b.first > lh.top()) {
                    hh.push(b.first);
                    hs += b.first;
                } else {
                    lh.push(b.first);
                    ls += b.first;
                }
                if (b.second > lh.top()) {
                    hh.push(b.second);
                    hs += b.second;
                } else {
                    lh.push(b.second);
                    ls += b.second;
                }
                if (lh.size() > hh.size()) {
                    int tmp = lh.top();
                    ls -= tmp;
                    hs += tmp;
                    lh.pop();
                    hh.push(tmp);
                } else if (lh.size() < hh.size()) {
                    int tmp = hh.top();
                    hs -= tmp;
                    ls += tmp;
                    hh.pop();
                    lh.push(tmp);
                }
                // cout << b.first << " " << b.second << "\n";
            }
            if (q == 0) lh_s[ptr] = hs - ls; else hh_s[ptr] = hs - ls;
        }
        // for (auto v : lh_s) {
        //     cout << "l" << v << "\n";
        // }
        // for (auto v : hh_s) {
        //     cout << "h" << v << "\n";
        // }

        ll bs = 0x7FFFFFFFFFFFFFFFLL;

        for (int i = 0; i < n+1; i++) {
            bs = min(bs, lh_s[i] + hh_s[i]);
        }

        sum += bs;

        cout << sum << "\n";

        return 0;
    }

    vector<int> a;
    ll sum = 0;

    for (int i = 0; i < n; i++) {
        char sa, sb;
        int ia, ib;
        cin >> sa >> ia >> sb >> ib;
        if (sa == sb) {
            sum += abs(ia-ib);
            continue;
        }
        a.push_back(ia);
        a.push_back(ib);
        sum += 1;
    }

    sort(a.begin(), a.end());
    int p = a[a.size() / 2];

    for (auto v : a) {
        sum += abs(v-p);
    }

    cout << sum << "\n";
}

컴파일 시 표준 에러 (stderr) 메시지

bridge.cpp: In function 'int main()':
bridge.cpp:48:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |                 for (int i = 0; i < a.size()/2; i++) {
      |                                 ~~^~~~~~~~~~~~

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