Submission #1105270

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105270		Faggi	Sails (IOI07_sails)	C++11	25 / 100	244 ms	9504 KiB

sails

#include <bits/stdc++.h>
#define ll long long
using namespace std;

vector<ll> tamDP;  // Cantidad máxima de velas por altura
vector<ll> calcs;  // Ineficiencia acumulada por cantidad de velas
ll tam;

// Verifica si es posible distribuir las velas con un límite x
bool can(vector<ll> dp, ll x) {
    ll sobrante = 0;
    priority_queue<pair<ll, ll>> sum, res;  // Para manejar sobrantes y espacios

    for (ll i = tam; i > 0; i--) {
        ll maximo = min(x, tamDP[i]);

        // Si hay más velas de las permitidas, genera un sobrante
        if (dp[i] > maximo) {
            sobrante = dp[i] - maximo;
            dp[i] = maximo;
            if (i > 1) 
                sum.push({i, sobrante});
            else 
                return false;
        } 
        // Si sobra espacio, lo almacenamos
        else {
            res.push({i, maximo - dp[i]});
        }
    }

    sobrante = 0;

    // Emparejamos sobrantes con espacios disponibles
    while (!sum.empty() && !res.empty()) {
        ll pos = sum.top().first;
        sobrante += sum.top().second;
        sum.pop();

        // Elimina espacios que ya no se pueden usar
        while (!res.empty() && res.top().first > pos) 
            res.pop();

        // Ajusta los sobrantes
        while (!res.empty() && sobrante > 0) {
            ll posR = res.top().first;
            ll espacio = res.top().second;
            res.pop();

            if (sobrante <= espacio) {
                res.push({posR, espacio - sobrante});
                sobrante = 0;
            } else {
                sobrante -= espacio;
            }
        }

        if (sobrante > 0) return false;
    }

    return sum.empty() && sobrante == 0;
}

// Calcula la ineficiencia mínima con un límite x
ll calc(vector<ll> dp, ll x) {
    priority_queue<pair<ll, ll>> pq;
    ll ret = 0;

    // Llena la cola con las diferencias entre el límite y las velas actuales
    for (ll i = tam; i > 0; i--) {
        if (dp[i] < min(x, tamDP[i])) {
            pq.push({i, min(x, tamDP[i]) - dp[i]});
        }
    }

    // Redistribuye las velas para minimizar la ineficiencia
    for (ll i = tam; i > 0; i--) {
        while (!pq.empty() && pq.top().first > i) 
            pq.pop();

        while (dp[i] > min(x, tamDP[i])) {
            ll rest = min(dp[i] - min(x, tamDP[i]), pq.top().second);
            dp[i] -= rest;
            dp[pq.top().first] += rest;

            if (pq.top().second - rest > 0) {
                pq.push({pq.top().first, pq.top().second - rest});
            } else {
                pq.pop();
            }
        }
    }

    // Calcula la ineficiencia total
    for (ll i = tam; i > 0; i--) {
        ret += calcs[dp[i]];
    }

    return ret;
}

int main() {
    ll n;
    cin >> n;

    calcs.resize(n + 1);
    calcs[0] = 0;
    calcs[1] = 0;

    // Calcula la ineficiencia acumulada
    for (ll i = 2; i <= n; i++) {
        calcs[i] = calcs[i - 1] + (i - 1);
    }

    vector<pair<ll, ll>> v(n);
    tam = 0;

    // Lee los mástiles y calcula la altura máxima
    for (ll i = 0; i < n; i++) {
        cin >> v[i].first >> v[i].second;
        tam = max(tam, v[i].first);
    }

    vector<ll> dp(tam + 1, 0);
    tamDP.resize(tam + 1, 0);

    // Inicializa los valores de DP y tamDP
    for (ll i = 0; i < n; i++) {
        dp[v[i].first]++;
        dp[v[i].first - v[i].second]--;
        tamDP[v[i].first]++;
    }

    ll ma = dp[tam];

    // Acumula los valores en dp y tamDP
    for (ll i = tam - 1; i >= 0; i--) {
        dp[i] += dp[i + 1];
        ma = max(ma, dp[i]);
        tamDP[i] += tamDP[i + 1];
    }

    ll mi = 0, pos = ma;

    // Búsqueda binaria para encontrar el valor mínimo posible
    while (mi <= ma) {
        ll piv = (mi + ma) / 2;
        if (can(dp, piv)) {
            ma = piv - 1;
            pos = piv;
        } else {
            mi = piv + 1;
        }
    }

    // Calcula y muestra la ineficiencia mínima
    cout << calc(dp, pos) << endl;

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10