SHARE
TWEET

SMMR Task_138 26/3/63

mickypinata Mar 26th, 2020 (edited) 64 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. typedef struct pos{
  6.     int row;
  7.     int col;
  8. }pos;
  9.  
  10. int table[11][11];
  11. bool place[11];
  12. vector<pos> tmp;
  13. vector<pos> ans;
  14. int t, x, sum, mx;
  15.  
  16. void PlaceRook(int row){
  17.     if(row > t){
  18.         if(sum > mx){
  19.             ans.clear();
  20.             ans = tmp;
  21.             mx = sum;
  22.         }
  23.         return;
  24.     } else {
  25.         for(int i = 1; i <= t; ++i){
  26.             if(!place[i]){
  27.                 sum += table[row][i];
  28.                 tmp.push_back({row, i});
  29.                 place[i] = true;
  30.                 PlaceRook(row + 1);
  31.                 sum -= table[row][i];
  32.                 tmp.pop_back();
  33.                 place[i] = false;
  34.             }
  35.         }
  36.         return;
  37.     }
  38. }
  39.  
  40. void PrintTable(){
  41.     for(int i = 1; i <= t; ++i){
  42.         for(int j = 1; j <= t; ++j){
  43.             cout << table[i][j] << " ";
  44.         }
  45.         cout << "\n";
  46.     }
  47. }
  48.  
  49. int main(){
  50.  
  51.     scanf("%d", &t);
  52.     for(int i = 1; i <= t; ++i){
  53.         for(int j = 1; j <= t; ++j){
  54.             scanf("%d", &x);
  55.             table[i][j] = x;
  56.         }
  57.     }
  58.  
  59.     mx = -2e9;
  60.     sum = 0;
  61.     PlaceRook(1);
  62.     cout << mx << "\n";
  63.     for(auto x : ans){
  64.         cout << x.row << " " << x.col << "\n";
  65.     }
  66.  
  67.     return 0;
  68. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top