Enunț

Prințesa Gîrcella este foarte frumoasă. Fiindcă a venit momentul să se mărite, foarte mulți feciori au venit să îi ceară mâna. Printre aceștia se află și Cavalerul de Aur, marele algoritmician. Gîrcella îl dorește pe cel mai inteligent, așa că le va pune o provocare. Grădina sa este o matrice pătratică binară (cu valori 0 sau 1), valorile 0 reprezintă teren liber iar valorile 1 reprezintă pomi. Cel ce va găsi suprafața dreptunghică de arie maximă ce conține doar valori 0, pe care va construi un hambar, va câștiga mâna frumoasei Gîrcella.

Cerința

Ajutați-l pe Cavalerul de Aur să câștige această întrecere.

Date de intrare

Fișierul de intrare hambar2.in conține pe prima linie numerele N și M, reprezentând dimensinunea matricei respectiv numărul de pomi, iar pe următoarele M linii se vor găsi două numere x și y, separate printr-un spațiu, reprezentând indicele liniei, respectiv al coloanei pe care se află un pom.

Date de ieșire

Fișierul de ieșire hambar2.out va conține pe prima linie numărul S, reprezentând aria maximă a unei suprafețe dreptunghiulare.

Restricții și precizări

1 ≤ N, M ≤ 1000
Nu se vor afla 2 sau mai mulți pomi în același loc.

Exemplu

hambar2.in

hambar2.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Hambar2:

/*
    Popa Bogdan Ioan, Colegiul National Aurel Vlaicu
    clasa a 10-a
    Sume partiale, O(N^2)
*/
#include <bits/stdc++.h>
#define nmax 1002
using namespace std;
ifstream fin("hambar2.in");
ofstream fout("hambar2.out");
int n, M;
int i, j, k;
int L;
bitset<nmax>a[nmax];
short S[nmax][nmax];
int maxarie;
short ct[nmax];
int idx;
int main()
{
    fin >> n >> M;
    while(M--)
    {
        fin >> i >> j;
        a[i][j] = 1;
    }
    for(j = 1; j <= n; j++)
    {
        for(i = 1, k = 0; i <= n; i++)
        {
            if(a[i][j] == 0)
                S[i][j] = 1 + S[i][j - 1];
            while(k && S[ct[k]][j] > S[i][j])
            {
                idx = ct[k--];
                maxarie = max(maxarie, (i - ct[k] - 1) * S[idx][j]);
            }
            ct[++k] = i;
        }
        while(k)
        {
            idx = ct[k--];
            maxarie = max(maxarie, (n - ct[k]) * S[idx][j]);
        }
    }
    fout << maxarie << "\n";
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1973 Hambar2

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1973 Hambar2 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1973 Hambar2