Pagini recente » Istoria paginii utilizator/unibuc1923 | Profil Stefan19 | Algoritmiada 2015 - Clasament Runda 1, Juniori | Cod sursa (job #1683052) | Cod sursa (job #1300079)
#include<iostream>
#include<fstream>
#define m_max 200
#define n_max 200
using namespace std;
int m, n, w[m_max+1][m_max+1][2], maxi[m_max+1], maxj[m_max+1], best[n_max+1];
char bmat[m_max+1][n_max+1];
int main() {
int temp, max1=-1, max2=-1, max=-1, k, i, j;
char junkchar;
ifstream in;
in.open("bmatrix.in");
in>>m>>n;
for(i=1;i<=m;i++) {
for(j=1;j<=n;j++) {
in>>bmat[i][j];
// cout<<bmat[i][j]<<" ";
}
// cout<<"\n";
}
in.close();
for(i=1;i<=m;i++) {
max1=0; max2=0;
for(k=1;k<=n;k++)
best[k]=bmat[i][k]-'0';
for(k=1;k<=n;k++)
if(best[k]==0) { //first k with 0
temp=0;
temp++;
for(++k;best[k]==0 && k<=n;k++)
temp++;
if(max1<temp) {
max2=max1;
max1=temp;
}
else if(max2<temp)
max2=temp;
} //exits k at 1
w[i][i][0]=max1;w[i][i][1]=max2;
for(j=i+1;j<=m;j++) {
max1=0; max2=0;
for(k=1;k<=n;k++)
if(best[k]==0 && bmat[j][k]-'0'==1)
best[k]=1;
for(k=1;k<=n;k++)
if(best[k]==0) { //first k with 0
temp=0;
temp++;
for(++k;best[k]==0 && k<=n;k++)
temp++;
temp*=j-i+1;
//cout<<temp<<"\n";
if(max1<temp) {
max2=max1;
max1=temp;
}
else if(max2<temp)
max2=temp;
} //exits k at 1
w[i][j][0]=max1;w[i][j][1]=max2;
if(maxj[j]<max1)
maxj[j]=max1;
}
}
maxj[1]=w[1][1][0];
for(i=n;i>=1;i--) {
max=-1;
for(j=i;j<=n;j++)
if(max<w[i][j][0])
max=w[i][j][0];
if(i<n && max<maxi[i+1])
max=maxi[i+1];
maxi[i]=max;
}
max=-1;
for(i=1;i<m;i++)
if(max<maxj[i]+maxi[i+1])
max=maxj[i]+maxi[i+1];
ofstream out;
out.open("bmatrix.out");
out<<max<<"\n";/*
for(i=1;i<=m;i++)
out<<maxj[i]<<" ";
out<<"\n";
for(j=1;j<=n;j++)
out<<maxi[i]<<" ";
out<<"\n";
out<<"\n";
for(i=1;i<=m;i++) {
for(j=1;j<=n;j++)
out<<w[i][j][0]<<" ";
out<<"\n";
}
out<<"\n";
for(i=1;i<=m;i++) {
for(j=1;j<=n;j++)
out<<w[i][j][1]<<" ";
out<<"\n";
}
out<<"\n";*/
out.close();
return 0;
}