Cod sursa(job #1988203)

Utilizator sichetpaulSichet Paul sichetpaul Data 2 iunie 2017 13:39:55
Problema Teren Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>

using namespace std;
int s[301][301];
int main()
{  int n,m,i,j,k,ii,jj,st,dr,mij,Max=0,x,sum;
    ifstream f("teren.in");
    ofstream g("teren.out");
    f>>n>>m>>k;
    for (i=1;i<=n;++i)
    for (j=1;j<=m;++j) {
        f>>x;
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;
    }
     st=1;
     dr=min(n,m);
     while (st<=dr) {
        mij=(st+dr)/2;
        bool ok=0;
        for (i=1;i<=n-mij+1;++i)
        for (j=1;j<=m-mij+1;++j) {
            ii=i+mij-1;
            jj=j+mij-1;
            sum=s[ii][jj]-s[ii][j-1]-s[i-1][jj]+s[i-1][j-1];
            if (sum<=k) {
                ok=1;
                break;
            }
        }
          if (ok) {
            st=mij+1;
            Max=max(Max,mij);
          }
           else dr=mij-1;
     }
        g<<Max*Max;
    return 0;
}