Submission #1309985

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309985		quollcucumber`	Netrpeljivost (COI23_netrpeljivost)	C++20	10 / 100	15 ms	2940 KiB

Main

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int arr[16][16];
int score(vector<bool> v) {
    if(!v[0] && v[1] && v[2]) {
        int a = 9;
    }
    int a[n];
    for(int i = 0; i < n; i++) {
        int l = 0, r=  n;
        int pos = 1;
        while(l + 1< r) {
            int mid = (l + r) / 2;
            if(i < mid) {
                if(v[pos-1]) {
                    r = mid;
                    pos = pos* 2 + 1;
                }else {
                    r = mid;
                    pos = pos *2;
                }
            }else {
                if(!v[pos-1]) {
                    l = mid;
                    pos = pos* 2 + 1;
                }else {
                    l = mid;
                    pos = pos *2;
                }
            }
        }
        a[pos - n] = i;
    }
    int total = 0;
    for(int i = 0; i < n -1; i++) {
        total += arr[a[i]][a[i+1]];
    }
    return total;
}
signed main(){
    cin >>n;
    for(int i = 0; i < n;i++) {
        for(int j = 0; j < n; j++) {
            cin >> arr[i][j];
        }
    }
    queue<vector<bool>> q;
    q.push({});
    for(int i = 0; i < n-1; i++) {
        int sz = q.size();
        for(int j = 0; j < sz; j++) {
            vector<bool> v = q.front();
            q.pop();
            v.push_back(true);
            q.push(v);
            v.pop_back();
            v.push_back(false);
            q.push(v);
        }
    }
    int minval = 1000000000000000;
    while(!q.empty()) {
        vector<bool> a = q.front();
        q.pop();
        minval = min(minval, score(a));
    }
    cout<<minval<<'\n';
    return 0;
}

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