| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1104989 | Faggi | Sails (IOI07_sails) | C++11 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
using namespace std;vector<ll> tamDP; // Máximo permitido por alturavector<ll> calcs; // Ineficiencia acumuladall tam; // Altura máxima de los mástiles// Verifica si es posible distribuir las velas con un máximo de 'x' velas por segmento.bool can(vector<ll> dp, ll x) { for (ll i = tam; i > 0; i--) { ll ma = min(x, tamDP[i]); // Máximo permitido en esta altura if (dp[i] > ma) { // Si hay más velas que las permitidas en 'x' ll sob = dp[i] - ma; // Exceso de velas dp[i] = ma; if (i > 1) { dp[i - 1] += sob; // Mueve el exceso al siguiente segmento inferior } else { return false; // No es posible distribuirlas correctamente } } } return true;}// Calcula la ineficiencia total dada una distribución con máximo 'x' velas por segmento.ll calc(vector<ll> dp, ll x) { ll res = 0; for (ll i = tam; i > 0; i--) { ll ma = min(x, tamDP[i]); // Máximo permitido en esta altura if (dp[i] > ma) { ll sob = dp[i] - ma; // Exceso de velas dp[i] = ma; dp[i - 1] += sob; // Mueve el exceso al siguiente segmento inferior } res += calcs[dp[i]]; // Suma la ineficiencia correspondiente } return res;}int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll n; cin >> n; // Inicializa la ineficiencia acumulada calcs.resize(n + 1, 0); for (ll i = 2; i <= n; i++) { calcs[i] = calcs[i - 1] + (i - 1); } vector<pair<ll, ll>> v(n); // Altura y número de velas en cada mástil tam = 0; // Inicializamos la altura máxima en 0 for (ll i = 0; i < n; i++) { cin >> v[i].first >> v[i].second; tam = max(tam, v[i].first); // Actualizamos la altura máxima } // Inicializamos los vectores dp y tamDP vector<ll> dp(tam + 1, 0); tamDP.resize(tam + 1, 0); // Procesamos las velas para cada mástil for (ll i = 0; i < n; i++) { dp[v[i].first] += v[i].second; tamDP[v[i].first]++; } // Realizamos acumulación hacia abajo en los vectores dp y tamDP for (ll i = tam - 1; i >= 0; i--) { dp[i] += dp[i + 1]; tamDP[i] += tamDP[i + 1]; } // Búsqueda binaria para encontrar el valor óptimo de 'x' ll mi = 0, ma = dp[0], pos = ma; while (mi <= ma) { ll piv = (mi + ma) / 2; if (can(dp, piv)) { pos = piv; // Intentamos minimizar más el valor ma = piv - 1; } else { mi = piv + 1; } } // Calculamos e imprimimos la ineficiencia mínima cout << calc(dp, pos) << '\n'; return 0;}