Submission #919428

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
9194282024-01-31 18:12:58NK_Netrpeljivost (COI23_netrpeljivost)C++17
100 / 100
436 ms91164 KiB
// 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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...