Submission #480113

#	Time	Username	Problem	Language	Result	Execution time	Memory
480113		ocarima	3D Histogram (COCI20_histogram)	C++14	0 / 110	1 ms	332 KiB

histogram

#include<bits/stdc++.h>

using namespace std;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define lli long long int
#define vi vector<int>
#define vlli vector<long long int>
#define pii pair<int, int>
#define plli pair<lli, lli>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repa(i, a, b) for(int i = (a); i >= (b); i--)
#define repv(x, v) for(auto x : v)
#define debug(x) cout << #x << " = " << x << endl
#define debugsl(x) cout << #x << " = " << x << ", "
#define debugarr(x, a, b) cout << #x << " = ["; rep(i, a, b) cout << x[i] << ", "; cout << "]\n"
#define pb push_back
#define nl "\n"

#define MAXN 200003
#define MAXLG 19

lli n, a[MAXN], b[MAXN], ga[MAXN], gb[MAXN], pot[MAXLG], res;

lli encuentraOptimo(lli li, lli ri, lli ld, lli rd){

    if (li > ri) return 0;

    lli mitad = (li + ri) / 2;
    lli tmp, ans;
    lli opt, posopt;

    // ITERA POR TODO EN RANGO BUSCANDO LA VENTANA ÓPTIMA PARA ESA MITAD
    opt = 0;
    rep(pos, ld, rd){
        tmp = min(ga[mitad], ga[pos]) * min(gb[mitad], gb[pos]) * (pos - mitad + 1);
        if (tmp >= opt){
            opt = tmp;
            posopt = pos;
        }
    }

    // UNA VEZ CON EL ÓPTIMO, REVISA AMBAS MITADES USANDO EL ÓPTIMO COMO LIMITE
    ans = max(opt, encuentraOptimo(li, mitad - 1, ld, min(rd, posopt)));
    ans = max(ans, encuentraOptimo(mitad + 1, ri, max(ld, posopt), rd));

    return ans;
}

lli divide_y_venceras(lli l, lli r){
    // MANEJA LOS RANGOS TRIVIALES (ANCHO <= 1)
    if (l > r) return 0;
    if (l == r) return a[l] * b[l];

    lli ans = 0;
    lli mitad = (l + r) / 2;

    lli tmp;

    // LA REGLA DE ORO DEL DIVIDE Y VENCERAS:
    // 1. La solución está enteramente en el lado izquierdo.
    // 2. La solución está enteramente en el lado derecho.
    // 3. La solución contiene a la mitad del rango.

    // 1. y 2. VE LO MEJOR DEL LADO IZQUIERDO Y LO MEJOR DEL LADO DERECHO.
    ans = max(divide_y_venceras(l, mitad - 1), divide_y_venceras(mitad + 1, r));

    // 3. ES NECESARIO PROBAR TODAS LAS OPCIONES QUE CONTIENEN A LA MITAD DEL RANGO.

    // NINGUN RANGO PUEDE TENER UN a O UN b MAYOR QUE LOS DE LA MITAD,
    // CONSTRUYE EL ARREGLO DE MÍNIMOS A PARTIR DE LA MITAD DEL RANGO HACIA LA IZQUIERDA Y LA DERECHA.
    ga[mitad] = a[mitad];
    gb[mitad] = b[mitad];
    rep(i, mitad + 1, r){
        ga[i] = min(a[i], ga[i - 1]);
        gb[i] = min(b[i], gb[i - 1]);
    }
    repa(i, mitad - 1, l){
        ga[i] = min(a[i], ga[i + 1]);
        gb[i] = min(b[i], gb[i + 1]);
    }

    // CONSIDERA EL CASO DE QUE LA MEJOR VENTANA SEA SOLO LA MITAD.
    ans = max(ans, a[mitad] * b[mitad]);

    // ENCUENTRA EL INICIO OPTIMO HACIENDO UN DIVIDE Y VENCERAS SOBRE EL LADO IZQUIERDO.
    ans = max(ans, encuentraOptimo(l, mitad, mitad, r));

    return ans;
}

int main()
{
    fastio;
    pot[0] = 1;
    rep(p, 1, MAXLG - 1) pot[p] = pot[p - 1] * 2;

    cin >> n;
    rep(i, 1, n) cin >> a[i] >> b[i];
    res = divide_y_venceras(1, n);
    reverse(a + 1, a + 1 + n);
    reverse(b + 1, b + 1 + n);
    res = max(res, divide_y_venceras(1, n));
    cout << res << nl;
}

Compilation message (stderr)

histogram.cpp: In function 'long long int divide_y_venceras(long long int, long long int)':
histogram.cpp:58:9: warning: unused variable 'tmp' [-Wunused-variable]
   58 |     lli tmp;
      |         ^~~
histogram.cpp: In function 'long long int encuentraOptimo(long long int, long long int, long long int, long long int)':
histogram.cpp:31:14: warning: 'posopt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |     lli opt, posopt;
      |              ^~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 90