#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
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;
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
