Submission #1095284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095284		dpsaveslives	Palembang Bridges (APIO15_bridge)	C++17	100 / 100	79 ms	7152 KiB

bridge

#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
const int MAXN = 1e5+5;
bool cmp(pair<int,int> a, pair<int,int> b){
    return a.f+a.s < b.f+b.s;
}
ll X[2][MAXN]; pair<int,int> dif[MAXN];
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int K,N; cin >> K >> N;
    ll ans = 0;
    vector<int> vec; int n = 1;
    for(int i = 0;i<N;++i){
        char p1,p2; int S,T; cin >> p1 >> S >> p2 >> T;
        if(p1 != p2){
            vec.push_back(S); vec.push_back(T);
            dif[n].f = S; dif[n].s = T; ++n; ++ans;
        }
        else{
            ans += abs(S-T);
        }
    }
    --n;
    if(K == 1){
        if(!vec.size()){
            cout << ans << "\n";
            return 0;
        }
        sort(vec.begin(),vec.end());
        int med = vec[vec.size()/2];
        for(int i = 1;i<=n;++i){
            ans += abs(dif[i].f-med)+abs(dif[i].s-med);
        }
        cout << ans << "\n";
    }
    else{
        sort(dif+1,dif+n+1,cmp);
        priority_queue<int,vector<int>,less<int>> pq1; priority_queue<int,vector<int>,greater<int>> pq2; //pq1: decreasing, pq2: increasing
        ll lsum = 0, rsum = 0;
        for(int i = 1;i<=n;++i){
            pq1.push(dif[i].f); pq1.push(dif[i].s);
            lsum += dif[i].f+dif[i].s; rsum += pq1.top(); lsum -= pq1.top();
            pq2.push(pq1.top()); pq1.pop();
            if(pq1.top() > pq2.top()){
                int tmp1 = pq1.top(), tmp2 = pq2.top();
                pq1.pop(); pq2.pop();
                pq1.push(tmp2); pq2.push(tmp1);
                lsum += tmp2-tmp1; rsum -= tmp2-tmp1;
            }
            X[0][i] = rsum-lsum; //distance of the median to everything
        }
        while(!pq1.empty()){
            pq1.pop();
        }
        while(!pq2.empty()){
            pq2.pop();
        }
        lsum = rsum = 0;
        for(int i = n;i>=1;--i){
            pq1.push(dif[i].f); pq1.push(dif[i].s);
            lsum += dif[i].f+dif[i].s; rsum += pq1.top(); lsum -= pq1.top();
            pq2.push(pq1.top()); pq1.pop();
            if(pq1.top() > pq2.top()){
                int tmp1 = pq1.top(), tmp2 = pq2.top();
                pq1.pop(); pq2.pop();
                pq1.push(tmp2); pq2.push(tmp1);
                lsum += tmp2-tmp1; rsum -= tmp2-tmp1;
            }
            X[1][i] = rsum-lsum;
        }
        ll val = 1e18;
        for(int i = 1;i<=n+1;++i){
            val = min(val,X[0][i-1]+X[1][i]); //first bridge for the first i-1, second for the others
        }
		cout << val+ans << "\n";
    }
    /*2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7*/
    return 0;
}

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