Submission #919428

#	Time	Username	Problem	Language	Result	Execution time	Memory
919428		NK_	Netrpeljivost (COI23_netrpeljivost)	C++17	100 / 100	436 ms	91164 KiB

Main

// 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;

	exit(0-0);
}

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