Pagini recente » Cod sursa (job #2331608) | Cod sursa (job #3224825) | Cod sursa (job #1894893) | Cod sursa (job #2901872) | Cod sursa (job #717069)
Cod sursa(job #717069)
#include <fstream>
#include <bitset>
#include <iostream>
#include <cmath>
using namespace std;
bitset<16> what_to_flip;
/** This is where our elements will be stored */
int matrix[16][16];
int lin,col;
ostream& operator << (ostream &out,const bitset<16> &bit)
{
out<<bit.to_string<char,char_traits<char>,allocator<char> >();
return out;
}
void add_1()
{
int i=0;
while(what_to_flip[i]==1)
what_to_flip[i++]=0;
what_to_flip[i]=1;
}
inline void flip_line(int line)
{
for(int i=0; i<col; i++)
matrix[line][i]*=(-1);
}
inline int get_sum()
{
int sum=0;
for(int i=0; i<lin; i++)
for(int j=0; j<col; j++)
sum+=matrix[i][j];
return sum;
}
/** Will traverse every column and check if sum is negative. If it is negative, flip the column and add the result
@param this_sum - sum calculated without flipping columns
@return - maximum sum for this configuration
*/
inline int get_minimum_sum(int this_sum)
{
for(int i=0; i<col; i++)
{
int sumcol=0;
for(int j=0; j<lin; j++)
sumcol+=matrix[j][i];
if(sumcol<0)
{
this_sum-=sumcol;
sumcol*=-1;
this_sum+=sumcol;
}
}
return this_sum;
}
int main()
{
ifstream fin("flip.in");
ofstream fout("flip.out");
fin>>lin>>col;
/** Maximum sum is here */
int summax=0x80000000;
for(int i=0; i<lin; i++)
for(int j=0; j<col; j++)
fin>>matrix[i][j];
int flips=pow(2,lin);
/** We now make flips to these lines*/
for(int i=0; i<flips; i++)
{
/**Flip the specified lines*/
for(int i=0; i<lin; i++)
if(what_to_flip[i]==1)
flip_line(i);
int temp_sum=0;
temp_sum=get_sum();
temp_sum=get_minimum_sum(temp_sum);
if(temp_sum>summax)
summax=temp_sum;
/** Flip them back */
for(int i=0; i<lin; i++)
if(what_to_flip[i]==1)
flip_line(i);
add_1();
}
fout<<summax;
return 0;
}