Submission #1129747

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129747		gyg	Netrpeljivost (COI23_netrpeljivost)	C++20	27 / 100	597 ms	129828 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define arr array 
#define vec vector
#define hmap unordered_map
const int N = 128 + 5, INF = 1e18;

int n;
arr<arr<int, N>, N> cst;

arr<arr<arr<hmap<int, int>, N>, N>, N> dp;
int slv(int lw, int hg, int lf, int rg) {
    if (lf > rg) swap(lf, rg);
    if (lw == hg) return 0;
    int md = (lw + hg) / 2;
    if (lf > md || rg <= md) return INF;
    if (dp[lw][hg][lf].count(rg)) return dp[lw][hg][lf][rg];

    int ans = INF;
    for (int x = lw; x <= md; x++) 
        for (int y = md + 1; y <= hg; y++) 
            ans = min(ans, cst[x][y] + slv(lw, md, lf, x) + slv(md + 1, hg, y, rg));
    dp[lw][hg][lf][rg] = ans;
    return ans;
}

signed main() {
    // freopen("a.in", "r", stdin);
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> cst[i][j];
    
    int ans = INF;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            ans = min(ans, slv(1, n, i, j));
    cout << ans << endl;
}

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