Cod sursa(job #1338446)

Utilizator aimrdlAndrei mrdl aimrdl Data 10 februarie 2015 01:51:11
Problema Jocul Flip Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 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;
}

void csums (int **mat, int m, int n) {
	for (int j = 0; j < n; j++) {
		mat[m][j] = 0;
		for (int i = 0; i < m; i++) {
			mat[m][j] += mat[i][j];
		}
	}
}

inline int csum (int **mat, int m, int n) {
	int s = 0;
	for (int j = 0; j < n; j++) {
		s += mat[m][j];
	}
	
	return abs(s);
}

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 += mat[i][n];
	}
	
	return abs(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]);
	}	
	
	csums(mat, m, n);
	int smax = csum(mat, m, n);
	
	for (int i = 0; i < (1 << n); i++) {
		cflip(buf, mat, m, n, i);
		//print(buf, m+1, n);
		csums(buf, m, n);
		int s = csum(buf, m, n);
		//printf("%d\n", s);
		if (s > smax) {
			copy(mat, buf, m, n);
			smax = s;
		}
	}
	
	for (int i = 0; i < (1 << m); 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;
}