Cod sursa(job #1041353)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 25 noiembrie 2013 19:25:35
Problema BMatrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <fstream>
#include <cstring>

using namespace std;
char a[205][205];
int dp[205][205] , s[205][205] , n, m, sol = 0;
inline void Read()
{
    ifstream f("bmatrix.in");
    f >> n  >> m;
    for(register int i = 1;i <= n; ++i)
        f>>(a[i]+1);
    f.close();
}

inline void Rotate(char a[][205])
{
    char C[205][205];
    register int  i, j;
    memcpy(C,a,sizeof(C));
    for(i = 1;i <= m; ++i)
        for(j = 1;j <= n; ++j)
            a[i][j] = C[j][m-i+1];
    swap(n,m);
}

inline void Init()
{
    register int i,j;
    for(i = 1;i <= n;++i)
        for(j = 1;j <= n; ++j)
            dp[i][j] = -1;
}

inline int DP(const int i,const int j)
{
    if(i>j)
        return 0;
    if(dp[i][j]>=0)
        return dp[i][j];
    dp[i][j] = max(DP(i+1,j),DP(i,j-1));
    int best = 0;
    for(int ind = 1;ind <= m; ++ind)
    {
        if(s[j][ind]-s[i-1][ind])
            best = 0;
        else
            ++best;
        dp[i][j] = max(best*(j-i+1),dp[i][j]);
    }
    return dp[i][j];
}

inline void DP()
{
    register int i,j;
    for(i = 1;i <= n; ++i)
        for(j = i;j <= n; ++j)
            dp[i][j] = DP(i,j);
}

inline int Result()
{
    register int best  = 0, i;
    for(i = 1;i < n;++i)
        best = max(best,dp[1][i]+dp[i+1][n]);
    return best;
}

inline void Partial_Sums()
{
    register int i,j;
    for(i = 1;i <= n; ++i)
        for(j = 1;j <= m; ++j)
            s[i][j] = s[i-1][j] + a[i][j] - '0';
}

inline void Solve()
{
    Partial_Sums();
    Init();
    DP();
    sol = Result();
    Rotate(a);
    Partial_Sums();
    Init();
    DP();
    sol = max(sol,Result());
}

inline void Write()
{
    ofstream g("bmatrix.out");
    g<<sol<<"\n";
    g.close();
}
int main()
{
    Read();
    Solve();
    Write();
    return 0;
}