Submission #1129746

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129746		gyg	Netrpeljivost (COI23_netrpeljivost)	C++20	10 / 100	1595 ms	1740 KiB

Main

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

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

map<vec<int>, int> dp;
int slv(int lw, int hg, int lf, int rg) {
    if (lf > rg) swap(lf, rg);
    assert(lw <= lf && rg <= hg);
    if (lw == hg) return 0;
    int md = (lw + hg) / 2;
    if (lf > md || rg <= md) return INF;
    if (dp.count({lw, hg, lf, 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: 0 / 17
• Subtask 3: 0 / 32
• Subtask 4: 0 / 41