Pagini recente » Cod sursa (job #2539461) | Cod sursa (job #1905566) | Cod sursa (job #648742)
Cod sursa(job #648742)
#include <cstdio>
#include <iostream>
#include <fstream>
using namespace std;
long int sol=0,total;
int nrLinii,nrColoane;
long int a[100][16];
int i,j;
long int aux[100];
long int value(long int a[100],int size)
{
long int s = 0;
for (int i=1;i<=size;i++)
s += (long int) a[i];
return s;
}
long int flippedValue(long int a[100],int size)
{
long int s = 0;
for (int i=1;i<=size;i++)
s += (long int) -a[i];
return s;
}
long int back(int n)
{total=0;
if (n > nrLinii)
return sol;
else
{
for ( i=1;i<=nrColoane;i++)
{
for (j=1;j<=nrLinii;j++)
aux[j] = a[j][i];
//cout << "Normal line "<< n << " column " << i << " normal value " << value(aux,nrLinii) << endl;
//cout << "Normal line "<< n << " column " << i << " flipped value " << flippedValue(aux,nrLinii) << endl;
if ( value(aux,nrLinii) > flippedValue(aux,nrLinii) )
{
total += (long int) value(aux,nrLinii);
}
else
{
total += (long int) flippedValue(aux,nrLinii);
for (j=1;j<=nrLinii;j++)
a[j][i] = -aux[j];
}
}
if (total > sol) {sol = total;}
//cout << "Normal line "<< n << " total : " << total << endl;
total = 0;
for ( j=1;j<=nrColoane;j++)
{
a[n][j] = -a[n][j];
}
for ( i=1;i<=nrColoane;i++)
{
for (j=1;j<=nrLinii;j++)
aux[j] = a[j][i];
//cout << "Flipped line "<< n << " column " << i << " normal value " << value(aux,nrLinii) << endl;
//cout << "Flipped line "<< n << " column " << i << " flipped value " << flippedValue(aux,nrLinii) << endl;
if ( value(aux,nrLinii) > flippedValue(aux,nrLinii) )
{
total += (long int) value(aux,nrLinii);
}
else
{
total += (long int) flippedValue(aux,nrLinii);
for (j=1;j<=nrLinii;j++)
a[j][i] = -aux[j];
}
}
if (total > sol) {sol = total;}
else
{
for ( j=1;j<=nrColoane;j++)
{
a[n][j] = -a[n][j];
}
}
//cout << "Flipped line "<< n << " total : " << total << endl;
return back(n+1);
}
}
int main()
{
FILE* f = fopen("flip.in","r");
fscanf(f,"%d %d",&nrLinii,&nrColoane);
for (int i=1;i<=nrLinii;i+=1)
for (int j=1;j<=nrColoane;j+=1)
fscanf(f,"%ld",&a[i][j]);
fclose(f);
//cout << a[1][1] << endl << a[13][2] << endl;
ofstream out; out.open("flip.out");
out << back(1);
out.close();
return 0;
}