제출 #566625

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
566625		ac2hu	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	2072 ms	340 KiB

bridge

#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else 
#define deb(x...)
#endif
using namespace std;
#define int long long 
signed main() {
    iostream::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int n,k;cin >> k >> n;
    vector<pair<int,int>> loc;
    int same_part = 0;
    int mx = 0;
    for(int i = 0;i<n;i++){
        char c1, c2;
        int a,b;
        cin >> c1 >> a >> c2 >> b;
        if(c1 == c2){
            same_part += abs(a - b);
        }
        else{
            mx = max(mx, max(a, b));
            same_part++;
            if(a > b)swap(a, b);
            loc.emplace_back(a, b);
        }
    }
    deb(loc);
    multiset<pair<int,int>> aset, bset;
    for(auto e : loc)aset.insert(e);
    int ans = 1e18;
    int sump1 = 0;
    int sump2 = 0;
    int sump3 = 0;
    int inp2 = 0;
    for(auto e : aset)sump1 += e.first + e.second;
    set<pair<int,int>> extra;
    for(int i = 0;i<=mx;i++){
        while(aset.size() > 0){
            auto it = *aset.begin();
            if(i >= it.first){
                bset.insert({it.second, it.first});
                aset.erase(aset.begin());
                sump1 -= it.first + it.second;
                sump3 += abs(it.first - it.second);
            }
            else
                break;
        }
        while(bset.size() > 0){
            auto it = *bset.begin();
            if(i >= it.first){
                bset.erase(bset.begin());
                extra.insert(it);
                sump2 += it.first + it.second;
                sump3 -= abs(it.first - it.second);
                inp2++;
            }
            else break;
        }
        deb(aset, bset, extra);
        int p1 = sump1 - 2*i*aset.size();
        int p2 = inp2*2*i - sump2;
        deb(same_part, p1, p2, sump3);
        ans = min(ans, same_part + (sump1 - 2*i*(int)aset.size()) + (inp2*2*i - sump2) + sump3);
    }
    cout << ans << "\n";
}

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

bridge.cpp: In function 'int main()':
bridge.cpp:64:13: warning: unused variable 'p1' [-Wunused-variable]
   64 |         int p1 = sump1 - 2*i*aset.size();
      |             ^~
bridge.cpp:65:13: warning: unused variable 'p2' [-Wunused-variable]
   65 |         int p2 = inp2*2*i - sump2;
      |             ^~

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