Submission #1018749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018749		MarwenElarbi	Netrpeljivost (COI23_netrpeljivost)	C++17	100 / 100	1202 ms	123696 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define pb push_back
#define se second
#define fi first
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int nax=2050;
int cost [nax][nax];
long long dp1[nax][nax];
long long dp[nax][nax];
void solve(int l,int r){
    if(l+1==r){
        dp[l][r]=dp[r][l]=cost[l][r];
        return;
    }
    int mid=(r+l)/2;
    solve(l,mid);
    solve(mid+1,r);
    for (int i = l; i <= mid; ++i)
    {
        for (int j1 = mid+1; j1 <= (mid+1+r)/2; ++j1)
        {
            for (int j2 = (mid+1+r)/2+1; j2 <= r; ++j2)
            {
                dp1[i][j1]=min(dp1[i][j1],dp[j1][j2]+cost[i][j2]);
                dp1[i][j2]=min(dp1[i][j2],dp[j1][j2]+cost[i][j1]);
            }
        }
    }
    for (int i1 = l; i1 <= (l+mid)/2; ++i1)
    {
        for (int i2 = (l+mid)/2+1; i2 <= mid; ++i2)
        {
            for (int j = mid+1; j <= r; ++j)
            {
                dp[i1][j]=min(dp[i1][j],dp1[i2][j]+dp[i1][i2]);
                dp[i2][j]=min(dp[i2][j],dp1[i1][j]+dp[i1][i2]);
            }
        }
    }
    for (int i = l; i <= mid; ++i)
    {
        for (int j = mid+1; j <= r; ++j)
        {
            dp[j][i]=dp[i][j];
        }
    }
}
int main() {/*
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif*/
    optimise;
    int n;
    cin>>n;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            dp[i][j]=dp1[i][j]=1e18;
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin>>cost[i][j];
        }
    }
    long long ans=1e18;
    solve(0,n-1);
    for (int i = 0; i <= (n-1)/2; ++i)
    {
        for (int j = (n-1)/2+1; j <= n-1; ++j)
        {
            ans=min(ans,min(dp[i][j],dp[j][i]));
        }
    }
    cout <<ans<<endl;
}

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