Submission #971362

#	Time	Username	Problem	Language	Result	Execution time	Memory
971362		HuyAT	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	125 ms	12200 KiB

bridge

#include<bits/stdc++.h>
#define newl '\n'

const int MaxN = 1e5 + 10;
const int MaxV = 1e7 + 10;
const long long Inf = 1e18;
const long long Mod = 1e9 + 7;

struct MedianCost{
    std::multiset<int> s,s1;
    int cnt;
    long long t,t1;
    MedianCost() : cnt(0),t(0),t1(0){

    }
    void balance(){
        while((int)s.size() > (cnt + 1) / 2){
            auto it = prev(s.end());
            t -= *it;
            t1 += *it;
            s1.insert(*it);
            s.erase(it);
        }
        while((int)s.size() < (cnt + 1) / 2){
            auto it = s1.begin();
            t += *it;
            t1 -= *it;
            s.insert(*it);
            s1.erase(it);
        }
    }
    void add(int x){
        if(cnt <= 2){
            s.insert(x);
            t += x;
        }else{
            if(x <= *prev(s.end())){
                s.insert(x);
                t += x;
            }else{
                s1.insert(x);
                t1 += x;
            }
        }
        ++cnt;
        balance();
    }
    long long cost(){
        long long mid = *prev(s.end());
        return mid * (long long)s.size() - t + t1 - mid * (long long)s1.size();
    }
};
std::vector<std::pair<int,int>> a{{0,0}};
int k,n;
long long total = 0;

void readData(){
    std::cin >> k >> n;
    for(int i = 1;i <= n;++i){
        char p,q;
        int s,t;
        std::cin >> p >> s >> q >> t;
        if(s > t){
            std::swap(s,t);
        }
        if(p == q){
            total += llabs(s - t);
        }else{
            a.emplace_back(s,t);
        }
    }
    std::sort(a.begin(),a.end());
    n = (int)a.size() - 1;
}
long long first(){
    MedianCost s;
    for(int i = 1;i <= n;++i){
        s.add(a[i].first);
        s.add(a[i].second);
    }
    return s.cost() + total + n;
}
long long solve(){
    std::vector<long long> pref(n + 1,0),suff(n + 1,0);
    MedianCost s;
    long long ans = Inf;
    for(int i = 1;i <= n;++i){
        s.add(a[i].first);
        s.add(a[i].second);
        pref[i] = s.cost();
    }
    s = MedianCost();
    for(int i = n;i >= 1;--i){
        s.add(a[i].first);
        s.add(a[i].second);
        suff[i] = s.cost();
    }
    for(int i = 1;i <= n;++i){
        if(i < n && k > 1){
            ans = std::min(ans,pref[i] + suff[i + 1]);
        }
        if(i == n){
            ans = std::min(ans,pref[i]);
        }
    }
    return pref[n] + total + n;
}
int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);std::cout.tie(nullptr);
    readData();
    std::cout << solve();

    return 0;
}

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