Submission #637960

#	Time	Username	Problem	Language	Result	Execution time	Memory
637960		BlancaHM	Palembang Bridges (APIO15_bridge)	C++14	22 / 100	105 ms	2056 KiB

bridge

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

long long unPuente(vector<int> & S, vector<int> & T) {
    int N = (int) S.size();
    if (N == 0) return 0;
    vector<int> posiciones(2*N);
    for (int i = 0; i < N; i++) {
        posiciones[2*i] = S[i];
        posiciones[2*i+1] = T[i];
    }
    sort(posiciones.begin(), posiciones.end());
    long long int posicionPuente = (posiciones[N - 1] + posiciones[N])/2;
    long long int total = (long long int) N;
    for (int i = 0; i < N; i++) {
        total += abs(S[i] - posicionPuente);
        total += abs(T[i] - posicionPuente);
    }
    return total;
}

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

long long int sumaIzq, sumaDer;

void incluirEnLaMediana(int a, priority_queue<int> & pqIzq,
    priority_queue<int, vector<int>, greater<int>> & pqDer) {
    if (a <= pqIzq.top()) {
        pqIzq.push(a);
        sumaIzq += a;
    } else {
        pqDer.push(a);
        sumaDer += a;
    }
    if (pqIzq.size() > pqDer.size() + 1) {
        int valor = pqIzq.top();
        pqIzq.pop();
        sumaIzq -= valor;
        pqDer.push(valor);
        sumaDer += valor;
    } else if (pqIzq.size() < pqDer.size()) {
        int valor = pqDer.top();
        pqIzq.push(valor);
        sumaIzq += valor;
        pqDer.pop();
        sumaDer -= valor;
    }
}

long long int dosPuentes(vector<int> & S, vector<int> & T) {
    int N = (int) S.size();
    if (N == 0) return 0;
    vector<pair<int, int>> posiciones(N);
    for (int i = 0; i < N; i++) {
        posiciones[i] = make_pair(S[i], T[i]);
    }
    sort(posiciones.begin(), posiciones.end(), comparador);
    priority_queue<int> pqIzq;
    priority_queue<int, vector<int>, greater<int>> pqDer;
    sumaIzq = 0, sumaDer = 0;
    vector<long long int> prefSumas(N);
    for (int i = 0; i < N; i++) {
        incluirEnLaMediana(posiciones[i].first, pqIzq, pqDer);
        incluirEnLaMediana(posiciones[i].second, pqIzq, pqDer);
        prefSumas[i] = sumaDer - sumaIzq;
    }
    long long int mejorPosible = prefSumas[N-1];
    pqIzq = priority_queue<int>();
    pqDer = priority_queue<int, vector<int>, greater<int>>();
    sumaIzq = 0;
    sumaDer = 0;
    for (int i = N-1; i > 0; i--) {
        incluirEnLaMediana(posiciones[i].first, pqIzq, pqDer);
        incluirEnLaMediana(posiciones[i].second, pqIzq, pqDer);
        mejorPosible = min(mejorPosible, sumaDer - sumaIzq + prefSumas[i-1]);
    }
    incluirEnLaMediana(posiciones[0].first, pqIzq, pqDer);
    incluirEnLaMediana(posiciones[0].second, pqIzq, pqDer);
    mejorPosible = min(mejorPosible, sumaDer - sumaIzq);
    return mejorPosible+N;
}

int main() {
    int K, N;
    cin >> K >> N;
    vector<int> S, T;
    long long int mismoLado = 0;
    for (int i = 0; i < N; i++) {
        char lado1, lado2;
        int pos1, pos2;
        cin >> lado1 >> pos1 >> lado2 >> pos2;
        if (lado1 == lado2) {
            mismoLado += abs(pos1-pos2);
        } else {
            S.push_back(pos1);
            T.push_back(pos2);
        }
    }
    if (K == 1) {
        cout << mismoLado + unPuente(S, T) << '\n';
    } else {
        cout << mismoLado + dosPuentes(S, T) << '\n';
    }
    return 0;
}

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