Submission #1014391

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014391		amine_aroua	Netrpeljivost (COI23_netrpeljivost)	C++17	100 / 100	1224 ms	123988 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
using namespace std;
#define intt long long
#define pb push_back
vector<vector<int>> mat;
int n ;
const intt INF = 1e18;
vector<vector<intt>> dp , dp_;
void solve(int l , int r)
{
    if(l + 1 == r)
    {
        dp[l][r] = dp[r][l] = mat[l][r];
        return ;
    }
    int m = (l + r)/2;
    solve(l , m);
    solve(m + 1,  r);
    for(int i = l ; i <= m ; i++)
    {
        for(int j1 = m + 1 ; j1 <= (m + 1 + r)/2 ; j1++)
        {
            for(int j2 = (m + 1 + r)/2  + 1; j2 <= r ; j2++)
            {
                dp_[i][j1] = min(dp_[i][j1] , dp[j1][j2] + mat[j2][i]);
                dp_[i][j2] = min(dp_[i][j2] , dp[j1][j2] + mat[j1][i]);
            }
        }
    }
    for(int i1 = l ; i1 <= (l + m)/2 ; i1++)
    {
        for(int i2 = (l + m)/2 + 1 ; i2 <= m ; i2++)
        {
            for(int j = m + 1 ; j <= r ; j++)
            {
                dp[i1][j] = min(dp[i1][j] , dp_[i2][j] + dp[i1][i2]);
                dp[i2][j] = min(dp[i2][j] , dp_[i1][j] + dp[i1][i2]);
            }
        }
    }
    for(int i = l ; i <=  m ; i++)
    {
        for(int j = m + 1 ; j <= r ; j++)
        {
            dp[j][i] = dp[i][j];
        }
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    mat = vector<vector<int>> (n , vector<int>(n));
    dp.assign(n , vector<intt>(n , INF));
    dp_ = dp;
    for(int i = 0 ; i < n ; i++)
    {
        for(int j = 0 ; j < n ; j++)
        {
            cin>>mat[i][j];
        }
    }
    if(n == 1)
    {
        cout<<0<<'\n';
        return 0;
    }
    intt ans = INF;
    solve(0 ,n - 1);
    int l = 0 , r = n - 1;
    int m = (l  + r)/2;
    for(int fr = l ; fr <= m ; fr++)
    {
        for(int bk = m + 1 ; bk <= r ; bk++)
        {
            ans = min({ans , dp[fr][bk] , dp[bk][fr]});
        }
    }
    cout<<ans<<'\n';
}

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