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.  
  23. int MaxNQueens(int col, vector<vector<int>>&grid) {
  24.  
  25.     if (col == N) {
  26.         return 0;
  27.     }
  28.  
  29.     int maximum = 0;
  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.             maximum = max(maximum, grid[row][col] + MaxNQueens(col+1, 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.     return maximum;
  49. }
  50.  
  51. void solve() {
  52.  
  53.     vector<vector<int>> grid(8, vector<int>(8));
  54.  
  55.     for (int i=0; i<N; i++) for (int j=0; j<N; j++) cin >> grid[i][j];
  56.  
  57.     cout << MaxNQueens(0, grid) << "\n";
  58.  
  59. }
  60.  
  61. int main()
  62. {
  63.     ios::sync_with_stdio(false);
  64.     cin.tie(nullptr), cout.tie(nullptr);
  65.  
  66.     ll t=1; cin >> t;
  67.     while (t--) { solve(); }
  68.  
  69.     return 0;
  70. }
  71.  
Success #stdin #stdout 0.01s 5296KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/C5m29a
language:
C++14 (gcc 8.3)
created:
14 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!