fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define PI 3.14159265359
  4. #define DP(x, y) memset(x, y, sizeof x)
  5. #define all(x) x.begin(), x.end()
  6. #define read(x) freopen("x", "r", stdin);
  7. #define write(x) freopen("x", "w", stdout);
  8.  
  9. using namespace std;
  10.  
  11. ll gcd(ll a,ll b) { while(b) { ll x = a; a = b; b = x % b; } return a; }
  12. ll lcm(ll a,ll b) { return a / gcd(a, b) * b; }
  13. ll nC2(ll n) { return (n)*(n-1)/2; }
  14. ll summing(ll n) { return (n)*(n+1); }
  15.  
  16. const int N = 8;
  17. int vis_col[50] = {0};
  18. int vis_row[50] = {0};
  19. int vis_right[50] = {0};
  20. int vis_left[50] = {0};
  21.  
  22. int ans=0;
  23.  
  24. void MaxNQueens(int col, int sum, vector<vector<int>>&grid) {
  25.  
  26.     if (col == N) {
  27.         ans = max(ans, sum);
  28.         return;
  29.     }
  30.  
  31.     for (int row=0; row<N; row++) {
  32.  
  33.         if ((vis_row[row] == 0) && (vis_left[col-row+N-1] == 0) && (vis_right[row+col] == 0)) {
  34.  
  35.             vis_row[row] = 1;
  36.             vis_left[col-row+N-1] = 1;
  37.             vis_right[row+col] = 1;
  38.  
  39.             MaxNQueens(col+1, sum + grid[row][col], grid);
  40.  
  41.             vis_row[row] = 0;
  42.             vis_left[col-row+N-1] = 0;
  43.             vis_right[row+col] = 0;
  44.  
  45.         }
  46.     }
  47. }
  48.  
  49. void solve() {
  50.  
  51.     vector<vector<int>> grid(N, vector<int>(N));
  52.  
  53.     for (int i=0; i<N; i++) for (int j=0; j<N; j++) cin >> grid[i][j];
  54.  
  55.     MaxNQueens(0, 0, grid);
  56.  
  57.     cout << ans << "\n";
  58.     ans=0;
  59.  
  60. }
  61.  
  62. int main()
  63. {
  64.     ios::sync_with_stdio(false);
  65.     cin.tie(nullptr), cout.tie(nullptr);
  66.  
  67.     ll t=1; cin >> t;
  68.     while (t--) { solve(); }
  69.  
  70.     return 0;
  71. }
  72.  
Success #stdin #stdout 0.01s 5252KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/hdhCTQ
language:
C++14 (gcc 8.3)
created:
13 days ago
visibility:
public

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!