Pagini recente » Monitorul de evaluare | Cod sursa (job #2382666) | Cod sursa (job #1701716) | Cod sursa (job #1505178) | Cod sursa (job #358755)
Cod sursa(job #358755)
#include<stdio.h>
#define infile "flip.in"
#define outfile "flip.out"
#define nmax 21
#define inf ~(1<<31)
int a[nmax][nmax]; //matricea cu numere
int n,m; //numarul de linii, respectiv coloane
int smax=(-1)*inf; //suma maxima ce se poate obtine
inline int max(int a, int b)
{
if(a>b) return a; return b;
}
inline void change(int p)
{ //inmultim cu (-1) valorile de pe linia p
int i;
for(i=1;i<=m;i++)
a[p][i]*=(-1);
}
inline void verif()
{
int s=0; //aici vom calcula suma
int i,j,k;
for(i=1;i<=m;i++) //luam fiecare coloana in parte
{
k=0; //aici vom calcula suma coloanei
for(j=1;j<=n;j++) //toate poitiile de pe coloana
k+=a[j][i]; //adaugam la suma
s+=max(k,(-1)*k); //adaugam la suma, maximul dintre normal, si dintre schimbat
}
if(s>smax) smax=s; //daca am obtinut o suma mai mare
}
void read()
{
int i,j;
scanf("%d %d\n",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&a[i][j]);
}
void bk(int p)
{
if(p>n) //daca am facut toate pozitiile
verif(); //vedem daca putem obtine suma mai mare
else
{
bk(p+1); //rezolvam mai departe cand nu schimbam linia p
change(p); //schimbam linia p
bk(p+1); //rezolvam mai departe cu linia p schimbata
change(p); //refacem linia p
}
}
void write()
{
printf("%d\n",smax);
}
int main()
{
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);
read();
bk(1);
write();
fclose(stdin);
fclose(stdout);
return 0;
}