Cod sursa(job #2781006)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 8 octombrie 2021 11:52:22
Problema Jocul Flip Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<cstdio>
#include<cstdlib>
int b[16][16],n,m,i,j,r,k,s,x,o=-900000000,t,l;
int U()
{
	int s,i,j;
	for(s=i=0;i<n;++i)
		for(j=0;j<m;++j)
			s+=b[i][j];
	return s;
}
void R(int r)
{
	int i;
	for(i=0;i<m;++i)
		b[r][i]=-b[r][i];
}
void C(int c)
{
	int i;
	for(i=0;i<n;++i)
		b[i][c]=-b[i][c];
}
int V(int c)
{
	int s,f,i;
	for(s=f=i=0;i<n;++i)
		s+=b[i][c],f+=-b[i][c];
	if(f>s)
        return f-s;
	return 0;
}
int W(int r)
{
	int s,f,i;
	for(s=f=i=0;i<m;++i)
		s+=b[r][i],f+=-b[r][i];
	if(f>s)
        return f-s;
	return 0;
}
int main()
{
	freopen("flip.in","r",stdin),freopen("flip.out","w",stdout),scanf("%d%d",&n,&m);
	for(i=0;i<n;++i)
		for(j=0;j<m;++j)
			scanf("%d",&b[i][j]);
	do {
		for(x=k=t=i=0;i<n;++i) {
			r=W(i);
			if(r>x)
                x=r,k=i;
		}
		for(j=0;j<m;++j) {
			r=V(j);
			if(r>x)
                x=r,k=j,t=1;
		}
		if(x>0) {
			if(!t)
                R(k);
			else
                C(k);
		} else {
			for(i=0;i<5;++i)
				R(random()%n),C(random()%m);
		}
		s=U();
		if(s>o)
            o=s;
		++l;
	} while(l<500);
	printf("%d",o);
	return 0;
}