Submission #332278

#	Time	Username	Problem	Language	Result	Execution time	Memory
332278		alien_lover	Palembang Bridges (APIO15_bridge)	C++14	0 / 100	1 ms	492 KiB

bridge

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <assert.h>

using namespace std;

typedef long long ll;

#define all(x) begin(x), end(x)
#define sz(x) (int) x.size()

const int PRIME = 1e9 + 7;


bool locationCmp(pair<int, int>& a, pair<int, int>& b){
    return a.first + a.second < b.first + b.second;
}

template<class T>
vector<int> calcDist(T start, T end, int size){
    vector<int> out(size);
    int ind = 0;
    multiset<int> smaller, bigger;
    smaller.insert(start->first); bigger.insert(start->second);
    int smallSum, bigSum;
    smallSum = start->first; bigSum = start->second;
    out[ind] = bigSum - smallSum;
    start++;
    while(start != end){
        smaller.insert(start->first);
        bigger.insert(start->second);
        smallSum += start->first;
        bigSum += start->second;

        while(*smaller.rbegin() > *bigger.begin()){
            int sumChange = *bigger.begin() - *smaller.rbegin();
            smallSum += sumChange;
            bigSum -= sumChange;
            bigger.insert(*smaller.rbegin());
            smaller.insert(*bigger.begin());
            bigger.erase(bigger.begin());
            smaller.erase(--smaller.end());
        }

        ind++;
        start++;

        out[ind] = bigSum - smallSum;        
    }
    return out;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    int k, n;
    cin >> k >> n;

    vector<pair<int, int>> paths;
    int sameSideAns = 0;

    for(int i = 0; i < n; i++){
        char side1, side2;
        int loc1, loc2;
        cin >> side1 >> loc1 >> side2 >> loc2;
        if(side1 == side2){
            sameSideAns += abs(loc1 - loc2);
            continue;
        }
        if(loc1 > loc2){
            swap(loc1, loc2);
        }
        // idk if this works
        assert(loc1 <= loc2);
        
        paths.push_back({loc1, loc2});
    }

    sort(all(paths), locationCmp);

    vector<int> fromLeft = calcDist(paths.begin(), paths.end(), sz(paths));

    if(k == 1){
        cout << sameSideAns + fromLeft[sz(paths)-1] + sz(paths) << '\n';
        return 0;
    }

    vector<int> fromRight = calcDist(paths.rbegin(), paths.rend(), sz(paths));

    int bridgeAns = INT32_MAX;

    for(int i = 0; i < sz(paths) - 1; i++){
        bridgeAns = min(bridgeAns, fromLeft[i] + fromRight[sz(paths) - i - 2]);
    }
    // for(int el: fromLeft){
    //     cout << el << ' ';
    // }
    // cout << '\n';
    // for(int el: fromRight){
    //     cout << el << ' ';
    // }
    // cout << '\n';



    cout << sameSideAns + bridgeAns + sz(paths) << '\n';
}

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