fork download
copy 
  1. /**
  2.  *  Description   : https://w...content-available-to-author-only...a.ro/problema/flip
  3.  *  Author's name : Adrian Statescu
  4.  *  License       : MIT Free to use and distribute as long as this note is kept.
  5.  *  Date          : Dec 10 2023 07:23
  6.  */
  7. #include <iostream>
  8. #define FIN "flip.in"
  9. #define FOUT "flip.out"
  10. #define SZ 17
  11.  
  12. using namespace std;
  13.  
  14. int stack[SZ],level,sum_max=0,
  15.     n, m, matrix[SZ][SZ],
  16.          _matrix[SZ][SZ];
  17.  
  18. void readdata(){
  19.   //freopen(FIN, "r", stdin);
  20.   cin>>n>>m;
  21.   for(int i = 1; i <= n; ++i) {
  22.     for(int j = 1; j <= m; ++j) {
  23.         cin>>matrix[i][j];
  24.     }
  25.   }
  26.   fclose(stdin);
  27. }
  28.  
  29. void writedata() {
  30.   //freopen(FOUT, "w", stdout);
  31.   cout<<sum_max;
  32.   fclose(stdout);
  33. }
  34.  
  35. void init() {
  36.   stack[level] = -1;
  37. }
  38.  
  39. int succ() {
  40.   if(stack[level] < 1) {
  41.     stack[level]++;
  42.     return 1;
  43.   }
  44.   return 0;
  45. }
  46.  
  47. int valid() {
  48.   return 1;
  49. }
  50.  
  51. void print() {
  52.   for(int i = 1; i <= n; ++i) {
  53.       cout<<stack[i]<<" ";
  54.   }
  55.   cout<<endl;
  56. }
  57.  
  58. int sol(){return level == n;}
  59.  
  60. void solve_flip() {
  61.   int s, stotal = 0;
  62.   // make a copy of the original matrix
  63.   for(int i = 1; i <= n; ++i) {
  64.     for(int j = 1; j <= m; ++j) {
  65.       _matrix[i][j] = matrix[i][j];
  66.     }
  67.   }
  68.  
  69.   //make flip on line
  70.   for(int i = 1; i <= n; ++i) {
  71.       for(int j = 1; j <= m; ++j)
  72.       if(stack[i] == 1){
  73.          _matrix[i][j] *= -1;
  74.       }
  75.   }
  76.  
  77.   for(int j = 1; j <= m; ++j) {
  78.       s = 0;
  79.       for(int i = 1; i <= n; ++i) {
  80.         s += _matrix[i][j];
  81.       }
  82.       if(s<0) s*=-1;
  83.       stotal += s;
  84.   }
  85.   if(sum_max<stotal)sum_max=stotal;
  86. }
  87.  
  88. void bk() {
  89. int s,v;
  90. level = 1;
  91. init();
  92. while(level>0){
  93.     s = 1;
  94.     v = 0;
  95.     while(s && !v){
  96.       s = succ();
  97.       if(s) {
  98.         v = valid();
  99.       }
  100.     }
  101.  
  102.     if(s){
  103.       if(sol()){
  104.         solve_flip();
  105.       } else {
  106.         level++;
  107.         init();
  108.       }
  109.     } else level--;
  110. }
  111.  
  112. }
  113.  
  114. int main(int argc, char const *argv[]) {
  115.   readdata();
  116.   bk();
  117.   writedata();
  118.   return 0;
  119. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
5 3
4 -2 2
3 -1 5
2 0 -3
4 1 -3
5 -3 2
stdout
copy 
28
https://ideone.com/q3N4Aw
Flip Problem
language:
C++ (gcc 8.3)
created:
149 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!