Cod sursa(job #348812)

Utilizator alin.predoiAlin Predoi alin.predoi Data 16 septembrie 2009 23:36:32
Problema Jocul Flip Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <iostream>
using namespace std;

 typedef vector<int> vi; 
 typedef vector<vi> vvi; 
 typedef pair<int,int> ii; 
 #define sz(a) int((a).size()) 
 #define pb push_back 
 #define all(c) (c).begin(),(c).end() 
 #define tr(c,i) for(typeof((c).begin() i = (c).begin(); i != (c).end(); i++) 
 #define present(c,x) ((c).find(x) != (c).end()) 
 #define cpresent(c,x) (find(all(c),x) != (c).end())
#define VMAX 1000
#define INFINITE 123456789
int fl[33], M, N;
long mat[17][17],sumamax=-INFINITE;

void read () {
	fstream f;
	f.open("flip.in", fstream::in);
	f>>M>>N;
	for (int i=1; i<=M; i++)
		for (int j=1; j<=N;j++)
			f>>mat[i][j];
	f.close();
}

long suma () {
	long s=0;
	for (int i=1; i<=M; i++)
		for (int j=1;j<=N;j++)
			s+=mat[i][j]*fl[i]*fl[M+j];
	return s;
}

int solution (int k) {
	return k==M+N;
}

void back(int k) {
	if (!solution(k)) {
		fl[k+1]=1;
		back(k+1);
		fl[k+1]=-1;
		back(k+1);
	} else {
		if (suma() > sumamax)
			sumamax=suma();
	}
}
void solve () {
	fstream g;
	back(0);
	g.open("flip.out", fstream::out);
	g<<sumamax;
	g.close();
}
int main() {
	read();
	solve();
return 0;
}