Submission #1104982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104982		Faggi	Sails (IOI07_sails)	C++11	25 / 100	43 ms	5080 KiB

sails

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

vector<ll> tamDP;
vector<ll> calcs;
ll tam;

// Función para verificar si es posible distribuir con el límite `x`.
bool can(vector<ll> dp, ll x) {
    ll ma, sob, i;
    for (i = tam; i > 0ll; i--) {
        ma = min(x, tamDP[i]);  // Máximo permitido en esta altura.
        sob = 0ll;
        if (dp[i] > ma) {
            sob = dp[i] - ma;
            dp[i] = ma;
            if (i > 1ll) {
                dp[i - 1ll] += sob;  // Propaga el sobrante hacia abajo.
            } else {
                return false;  // No es posible distribuir correctamente.
            }
        }
    }
    return true;
}

// Función para calcular la ineficiencia total.
ll calc(vector<ll> dp, ll x) {
    ll ma, sob, i, res = 0ll;
    for (i = tam; i > 0ll; i--) {
        ma = min(x, tamDP[i]);
        sob = 0ll;
        if (dp[i] > ma) {
            sob = dp[i] - ma;
            dp[i] = ma;
            dp[i - 1ll] += sob;
        }
    }
    // Suma las ineficiencias usando el vector `calcs`.
    for (i = tam; i > 0ll; i--) {
        res += calcs[dp[i]];
    }
    return res;
}

int main() {
    ll n, i, mi = 0ll, ma = 0ll, piv, pos;
    cin >> n;

    // Inicialización del vector `calcs`.
    calcs.resize(n + 1ll, 0ll);
    for (i = 2ll; i <= n; i++) {
        calcs[i] = calcs[i - 1ll] + (i - 1ll);
    }

    vector<pair<ll, ll>> v(n);
    for (i = 0ll; i < n; i++) {
        cin >> v[i].first >> v[i].second;
        tam = max(v[i].first, tam);
    }

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

    // Construcción de los vectores `dp` y `tamDP`.
    for (i = 0ll; i < n; i++) {
        dp[v[i].first] += 1ll;
        dp[v[i].first - v[i].second] -= 1ll;
        tamDP[v[i].first] += 1ll;
    }

    // Propagación de los valores hacia abajo.
    ma = dp[tam];
    for (i = tam - 1ll; i >= 0ll; i--) {
        dp[i] += dp[i + 1ll];
        ma = max(ma, dp[i]);
        tamDP[i] += tamDP[i + 1ll];
    }

    pos = ma;
    // Búsqueda binaria para encontrar el mínimo límite posible.
    while (mi <= ma) {
        piv = (mi + ma) / 2ll;
        if (can(vector<ll>(dp), piv)) {  // Usamos una copia de `dp`.
            ma = piv - 1ll;
            pos = piv;
        } else {
            mi = piv + 1ll;
        }
    }

    // Cálculo final de la ineficiencia.
    cout << calc(vector<ll>(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