Cod sursa(job #1338452)

Utilizator aimrdlAndrei mrdl aimrdl Data 10 februarie 2015 02:10:27
Problema Jocul Flip Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <stdio.h>
#include <string.h>
 
void print (int **mat, int m, int n) {
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			printf("%5d ", mat[i][j]);
		}
		printf("\n");
	}
}
 
inline int abs (int a) {
	return (a < 0) ? -a : a;
}
 
inline void cflip (int **buf, int **mat, int m, int n, int mask) {
	int col = 0;
	for (int i = 1; i < (2 << n); i <<= 1) {
		if (mask & i) {
			for (int i = 0; i < m; i++) {
				buf[i][col] = -mat[i][col];
			}
		} else {
			for (int i = 0; i < m; i++) {
				buf[i][col] = mat[i][col];
			}
		}
		++col;
	}
}
 
inline void rsums (int **mat, int m, int n) {
	for (int i = 0; i < m; i++) {
		mat[i][n] = 0;
		for (int j = 0; j < n; j++) {
			mat[i][n] += mat[i][j];
		}
	}
}
 
inline int rsum (int **mat, int m, int n) {
	int s = 0;
	for (int i = 0; i < m; i++) {
		s += abs(mat[i][n]);
	}
	 
	return s;
}
 
inline void rflip (int **buf, int **mat, int m, int n, int mask) {
	int row = 0;
	for (int i = 1; i < (2 << m); i <<= 1) {
		if (mask & i) {
			for (int j = 0; j < n; j++) {
				buf[row][j] = -mat[row][j];
			}
		} else {
			for (int j = 0; j < n; j++) {
				buf[row][j] = mat[row][j];
			}
		}
		row++;
	}
}
 
inline void copy (int **dest, int **source, int m, int n) {
	for (int i = 0; i < m + 1; i++) {
		memcpy(dest[i], source[i], n * sizeof(int));
	}
}
		 
	 
int main (void) {
	FILE *in = fopen("flip.in", "r");
	FILE *out = fopen("flip.out", "w");
	 
	int m, n;
	fscanf(in, "%d %d", &m, &n);
	 
	int **mat = new int * [m+1];
	for (int i = 0; i < m + 1; i++) {
		mat[i] = new int[n+1];
	}
	 
	int **buf = new int * [m+1];
  	for (int i = 0; i < m + 1; i++) {
		buf[i] = new int[n+1];
	}
	 
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n - 1; j++) {
			fscanf(in, "%d ", &mat[i][j]);
		}
		fscanf(in, "%d\n", &mat[i][n-1]);
	}  
	 
	rsums(mat, m, n);
	int smax = rsum(mat, m, n);
	int bestmask = 0;
	 
	for (int i = 0; i < (1 << n/2); i++) {
		cflip(buf, mat, m, n, i);
		//print(buf, m+1, n);
		rsums(buf, m, n);
		int s = rsum(buf, m, n);
		//printf("%d\n", s);
		if (s > smax) {
			bestmask = i;
			smax = s;
		}
	}
	
	cflip(mat, mat, m, n, bestmask);
	 
	for (int i = 0; i < (1 << m/2); i++) {
		rflip(buf, mat, m, n, i);
		//print(buf, m+1, n);
		rsums(buf, m, n);
		int s = rsum(buf, m, n);
		//printf("%d\n", s);
		if (s > smax) {
			smax = s;
		}
	}
	 
	fprintf(out, "%d", smax);
	 
	fclose(in);
	fclose(out);
	 
	return 0;
}