Submission #1015990

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015990		isaachew	Netrpeljivost (COI23_netrpeljivost)	C++17	100 / 100	334 ms	57964 KiB

Main

#include <bits/stdc++.h>
/*
 O(n^2 log n) what
 
 */

int main(){
  std::ios::sync_with_stdio(0);
  std::cin.tie(0);
    int n;
    std::cin>>n;
    std::vector<std::vector<int>> netrp(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            int x;
            std::cin>>x;
            netrp[i].push_back(x);
        }
    }
    std::vector<long long> ccosts(n);
    for(int i=1;i<n;i++){
        std::vector<long long> nccosts(n,1e18);
        for(int j=0;j<n;j++){
            for(int k=0;!(i&k);k++){
                nccosts[j^k^(i&-i)]=std::min(nccosts[j^k^(i&-i)],ccosts[j]+netrp[j][j^k^(i&-i)]);
            }
        }
        ccosts=nccosts;
    }
    long long mn=1e18;
    for(int i=0;i<n;i++)mn=std::min(mn,ccosts[i]);
    std::cout<<mn<<'\n';
}

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