제출 #372404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
372404		gozonite	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	120 ms	5100 KiB

bridge

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
typedef vector<pair<int, int>> vii;
typedef pair<int, int> pi;
#define MOD 1000000007LL

struct Data {
    int fi, si;
};
bool cmp(const Data& a, const Data& b) { return a.fi+a.si < b.fi+b.si; }

int K, N;
vector<Data> info;
int n;
multiset<ll> fl, fh, sl, sh;
ll fls = 0, fhs = 0, sls = 0, shs = 0;

void trans(ll x) {
    if (sl.find(x) != sl.end()) {
        sl.erase(sl.find(x)); sls -= x;
        if (sl.size()+1 < sh.size()) { auto it = sh.begin(); sls += *it; shs -= *it; sl.insert(*it); sh.erase(it); }
    } else if (sh.find(x) != sh.end()) {
        sh.erase(sh.find(x)); shs -= x;
        if (sh.size() < sl.size()) { auto it = sl.end(); it--; shs += *it; sls -= *it; sh.insert(*it); sl.erase(it); }
    }
    if (x >= *fh.begin()) {
        fh.insert(x); fhs += x;
        if (fl.size()+1 < fh.size()) { auto it = fh.begin(); fls += *it; fhs -= *it; fl.insert(*it); fh.erase(it); }
    } else {
        fl.insert(x); fls += x;
        if (fh.size() < fl.size()) { auto it = fl.end(); it--; fhs += *it; fls -= *it; fh.insert(*it); fl.erase(it); }
    }
}

int main() {
    //freopen("feast.in", "r", stdin);
    //freopen("feast.out", "w", stdout);
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    
    cin >> K >> N;
    
    ll pre = 0;
    for (int i = 0; i < N; i++) {
        char fc, sc; int fi, si;
        cin >> fc >> fi >> sc >> si;
        if (fc == sc) pre += abs(fi-si);
        else info.push_back({fi, si});
    }
    n = info.size();
    //cout << "pre: " << pre << endl;
    //cout << "info: ";
    //for (auto pp : info) cout << pp.fi << " " << pp.si << " | "; cout << endl;
    
    if (K == 1) {
        vector<int> v;
        for (auto pp : info) {
            v.push_back(pp.fi);
            v.push_back(pp.si);
        }
        sort(v.begin(), v.end());
        ll ans = info.size();
        for (int i = 0; i < v.size(); i++) ans += abs(v[i]-v[v.size()/2]);
        cout << ans+pre << endl;
        
        //cout << "Debugging v: " << v[v.size()/2] << endl;
        //for (int i = 0; i < v.size(); i++) cout << v[i] << " "; cout << endl;
    } else if (K == 2) {
        sort(info.begin(), info.end(), cmp);
        
        vector<int> v;
        for (auto pp : info) {
            v.push_back(pp.fi);
            v.push_back(pp.si);
        }
        sort(v.begin(), v.end());
        for (int i = 0; i < v.size()/2; i++) { sl.insert(v[i]); sls += v[i]; }
        for (int i = v.size()/2; i < v.size(); i++) { sh.insert(v[i]); shs += v[i]; }
        
        ll ans = 1e18;
        for (int i = 0; i < info.size()-1; i++) {
            trans(info[i].fi); trans(info[i].si);
            ll med = *fh.begin(), fs = ((ll)fl.size()*med - fls) + (fhs - (ll)fh.size()*med);
            med = *sh.begin(); ll ss = ((ll)sl.size()*med - sls) + (shs - (ll)sh.size()*med);
            ans = min(ans, fs+ss);
            
            //cout << "Debugging: " << i << " " << fs << " " << ss << endl;
            //for (auto pp : fl) cout << pp << " "; cout << ": " << fls << endl;
            //for (auto pp : fh) cout << pp << " "; cout << ": " << fhs << endl;
            //for (auto pp : sl) cout << pp << " "; cout << ": " << sls << endl;
            //for (auto pp : sh) cout << pp << " "; cout << ": " << shs << endl;
        }
        
        ans += info.size();
        cout << ans+pre << endl;
    }
}

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

bridge.cpp: In function 'int main()':
bridge.cpp:66:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for (int i = 0; i < v.size(); i++) ans += abs(v[i]-v[v.size()/2]);
      |                         ~~^~~~~~~~~~
bridge.cpp:80:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for (int i = 0; i < v.size()/2; i++) { sl.insert(v[i]); sls += v[i]; }
      |                         ~~^~~~~~~~~~~~
bridge.cpp:81:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int i = v.size()/2; i < v.size(); i++) { sh.insert(v[i]); shs += v[i]; }
      |                                  ~~^~~~~~~~~~
bridge.cpp:84:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for (int i = 0; i < info.size()-1; i++) {
      |                         ~~^~~~~~~~~~~~~~~

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