Cod sursa(job #805643)

Utilizator AthanaricCirith Gorgor Athanaric Data 31 octombrie 2012 20:27:11
Problema Jocul Flip Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <stdio.h>
int n,m,a[17][17];
char conf[20];
long long smax;
void modificare()
{  
	for(int i=1;i<=m;i++)  
	        if (conf[i]==1) 
						for(int j=1;j<=n;j++) 
										a[j][i]*=-1;  
										}  
										long long suma()
										{  
										    long long st,sp,sn;  
											    st=0;  
												    for(int i=1;i<=n;i++)
														{  
														        sp=sn=0;  
																        for(int j=1;j<=m;j++)  
																		            if(a[i][j]>0) 
																									sp+=a[i][j];  
																												else sn-=a[i][j];  
																												        if(sp>sn) st=st+sp-sn;  
																														           else st=st+sn-sp;  
																																       }  
																																	     
																																		     return st;  
																																			 } 
																																			 void bkt(int k)
																																			 {  
																																			 	if(k==m+1) 
																																					{  
																																					        modificare();  
																																							        long long sum=suma();  
																																									        if(sum>smax) 
																																														smax=sum;  
																																														        modificare();  
																																																	}  
																																																	    else  
																																																		    for(int i=0;i<=1;i++)
																																																				{  
																																																				        conf[k]=i;  
																																																						        bkt(k+1);  
																																																								    }  
																																																									}  
																																																									int main()
																																																									{
																																																										int i,j;
																																																											freopen("flip.in","r",stdin);
																																																												freopen("flip.out","w",stdout);
																																																													scanf("%d%d",&n,&m);
																																																														for (i=1; i<=n; i++)
																																																																for (j=1; j<=m; j++)
																																																																			scanf("%d",&a[i][j]);
																																																																				bkt(1);
																																																																					printf("%d ",smax);
																																																																						return 0;
																																																																						}