Submission #1067560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067560		MilosMilutinovic	Netrpeljivost (COI23_netrpeljivost)	C++14	100 / 100	461 ms	58196 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> a(n, vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> a[i][j];
    }
  }
  int lg = 0;
  for (int p = 1; p < n; p *= 2, lg++) {}
  const long long inf = (long long) 1e18;
  vector<long long> dp(n);
  for (int i = 0; i + 1 < n; i++) {
    vector<long long> new_dp(n, inf);
    for (int x = 0; x < n; x++) {
      int bit;
      for (int b = lg; b >= 0; b--) {
        if ((i >> b & 1) != ((i + 1) >> b & 1)) {
          bit = b;
          break;
        }
      }
      for (int xr = 0; xr < (1 << bit); xr++) {
        int y = (x ^ xr); 
        new_dp[y] = min(new_dp[y], dp[x] + a[(i ^ x)][(i + 1) ^ y]);
      }
    }
    swap(dp, new_dp);
  }
  cout << *min_element(dp.begin(), dp.end()) << '\n';
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:30:32: warning: 'bit' may be used uninitialized in this function [-Wmaybe-uninitialized]
   30 |       for (int xr = 0; xr < (1 << bit); xr++) {
      |                             ~~~^~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 17 / 17
• Subtask 3: 32 / 32
• Subtask 4: 41 / 41