Submission #1309976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309976		quollcucumber`	Netrpeljivost (COI23_netrpeljivost)	C++20	0 / 100	2 ms	824 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#define int long long
using namespace std;
int anti[128][128];
int arr[256][128][128];
int n;
void dp(int node, int l, int r) {
    if(l + 1 == r) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                arr[node][i][j] = INT_MAX;
            }
        }
        arr[node][l][l] = 0;
        return;
    }
    int mid = (l + r ) / 2;
    dp(node* 2, l, mid);
    dp(node * 2 +1, mid, r);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            arr[node][i][j] = INT_MAX;
        }
    }
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            for(int k = 0; k < n; k++) {
                for(int m = 0; m< n; m ++) {
                    arr[node][i][k] = min(arr[node * 2][i][j] + arr[node * 2 + 1][k][m] + anti[j][k], arr[node][i][k]);
                    arr[node][i][k] = min(arr[node * 2 + 1][i][j] + arr[node * 2][k][m] + anti[j][k], arr[node][i][k]);
                }
            }
        }
    }
}
signed main(){
    cin >> n;
    vector<pair<int, pair<int, int>>> edges;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> anti[i][j];
        }
    }
    int minval = INT_MAX;
    dp(1, 0, n);
    for(int i = 0; i < n; i++) {
        for(int j = 0; j <n; j++) {
            minval = min(minval, arr[1][i][j]);
        }
    }
    cout<<minval<<'\n';
    return 0;
}

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