Submission #919428

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
919428	2024-01-31 18:12:58	NK_	Netrpeljivost (COI23_netrpeljivost)	C++17	100 / 100	436 ms	91164 KiB

Main

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
using ll = long long;
template<class T> using V = vector<T>;
using vi = V<int>;
using vl = V<ll>;
int main() {
  cin.tie(0)->sync_with_stdio(0);
  
  int N; cin >> N;
  V<vi> A(N, vi(N)); for(auto& v : A) for(auto& x : v) cin >> x;
  
  V<vl> dp(N, vl(N));
  for(int i = 1; i < N; i++) {
    int b = i & (-i);
    for(int nx = 0; nx < N; nx++) {
      dp[i][nx] = ll(1e18);
      int l = (nx ^ b) & (~(b - 1)), r = l + b - 1;
      for(int x = l; x <= r; x++) dp[i][nx] = min(dp[i][nx], dp[i - 1][x] + A[nx][x]);
    }
  }
  cout << *min_element(begin(dp[N - 1]), end(dp[N - 1])) << nl;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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