Pagini recente » Cod sursa (job #1197569) | Cod sursa (job #1007495) | Cod sursa (job #1206168) | Cod sursa (job #2368808) | Cod sursa (job #1202183)
#include<iostream>
#include<fstream>
#define ll long long
using namespace std;
ll find_min(ll a[],ll n) {
ll pos=1;
for(ll i=2;i<=n;i++) {
if(a[i]<a[pos]) pos=i;
}
return pos;
}
int main()
{
ofstream fout ("flip.out");
ifstream fin ("flip.in");
ll r[20]={0},c[20]={0},i,j,temp,n,m,a[20][20]={0},sum_r=0,sum_c=0;
ll min_r,min_c,pos_r,pos_c;
fin>>n>>m;
for(i=1;i<=n;i++) {
for(j=1;j<=m;j++) fin>>a[i][j];
}
for(i=1;i<=n;i++) {
temp=0;
for(j=1;j<=m;j++) temp+=a[i][j];
r[i]=temp;
sum_r+=r[i];
}
for(j=1;j<=m;j++) {
temp=0;
for(i=1;i<=n;i++) temp+=a[i][j];
c[j]=temp;
sum_c+=c[j];
}
while(true) {
pos_r=find_min(r,n);
pos_c=find_min(c,m);
// cout<<r[pos_r]<<" "<<c[pos_c]<<endl;
if(r[pos_r]>=0 && c[pos_c]>=0) break;
else if(r[pos_r]<=c[pos_c]) {
// cout<<"it comes to row"<<endl;
if(sum_r-2*r[pos_r]>sum_c) {
sum_r=sum_r-2*r[pos_r];
sum_c=sum_r;
r[pos_r]=-1*r[pos_r];
// cout<<"value of c[i] ";
for(i=1;i<=m;i++) {
c[i]=c[i]-2*a[pos_r][i];
a[pos_r][i]=-1*a[pos_r][i];
}
}
else break;
}
else if(c[pos_c]<=r[pos_r]) {
// cout<<"it comes to column"<<endl;
if(sum_c+(-2*c[pos_c])>sum_r) {
sum_c=sum_c+(-2*c[pos_c]);
sum_r=sum_c;
c[pos_c]=-1*c[pos_c];
for(i=1;i<=n;i++) {
r[i]=r[i]-2*a[i][pos_c];
a[i][pos_c]=-1*a[i][pos_c];
}
}
else break;
}
/* for(i=1;i<=n;i++) cout<<r[i]<<" ";
cout<<endl;
for(i=1;i<=m;i++) cout<<c[i]<<" ";
cout<<endl;*/
}
// for(i=1;i<=n;i++) cout<<r[i]<<" ";
fout<<sum_r;
// system("pause");
return 0;
}