Cod sursa(job #2954836)

Utilizator inacioataCioata Ana Irina inacioata Data 15 decembrie 2022 16:44:51
Problema Teren Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("teren.in");
ofstream fout("teren.out");
/**
n = 1000..2000  n x n x (log n) operatii
n = 200..500    n^3 operatii
n = 100         n^4

6 8 1
0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 p
1 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 q
0 1 1 0 0 1 0 0
0 0 0 1 0 0 0 0

sume partiale pe coloane
0 0 0 1 0 0 0 0
0 1 0 1 0 0 0 0 p
1 1 0 1 0 0 1 0
1 1 0 2 0 0 1 0 q
1 2 1 2 0 1 1 0
1 2 1 3 0 1 1 1
*/

int a[303][303], t[303], n, m, X;

void Citire()
{
    int i,j;
    fin >> n >> m >> X;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
        {
            fin >> a[i][j];
            a[i][j] += a[i-1][j];
        }
}

/// lungimea maxima a unei secvente din t
/// care are suma elementelor <= X
int LungMax(int t[], int n, int X)
{
    int suma = 0, i, j, lenmax = 0;
    j = 1;
    for (i = 1; i <= n; i++)
    {
        suma += t[i];
        while (suma > X)
        {
            suma -= t[j];
            j++;
        }
        lenmax = max(lenmax, i - j + 1);
    }
    return lenmax;
}

void Rezolvare()
{
    int p, q, L, j, amax = 0;
    for (p = 1; p <= n; p++)
        for (q = p; q <= n; q++)
        {
            /// construim t:
            for (j = 1; j <= m; j++)
                t[j] = a[q][j] - a[p - 1][j];
            L = LungMax(t, m, X);
            amax =max(amax,L * (q - p + 1)) ;
        }
    fout<<amax<<"\n";
}

int main()
{
    int i,j;
    Citire();
    Rezolvare();
    fout.close();
    return 0;
}