oj.uz

Submission #1104982

# Submission time Handle Problem Language Result Execution time Memory
1104982 2024-10-25T03:27:19 Z Faggi Sails (IOI07_sails) C++11
25 / 100
 43 ms 5080 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 508 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 336 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1124 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 1636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 18 ms 2760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 4432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 4844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 43 ms 5080 KB Output isn't correct
2 Halted 0 ms 0 KB -