Submission #1106224

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106224		Zero_OP	Netrpeljivost (COI23_netrpeljivost)	C++14	100 / 100	374 ms	55624 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

#ifdef LOCAL
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
#endif // LOCAL

    int N;
    cin >> N;
    vector<vector<int>> cost(N, vector<int>(N, 0));
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            cin >> cost[i][j];
        }
    }

    const long long inf = 1e18;

    vector<long long> f(N, 0);

    int full = N - 1;
    for(int i = 1; i < N; ++i){
        vector<long long> g(N, inf);
        int lsb = i & (-i);
        for(int j = 0; j < N; ++j){
            int t = (j ^ lsb) & (full ^ (lsb - 1));
            for(int last = t; last < t + lsb; ++last){
                g[j] = min(g[j], f[last] + cost[last][j]);
            }
        }

        f = g;
    }

    long long ans = *min_element(f.begin(), f.end());
    cout << ans << '\n';

    return 0;
}

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