8256 2024. 01. 13 20:41:12 szil Festés (50 pont) cpp17 Elfogadva 50/50 209ms 43540 KiB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 200'001;

ll c[MAXN][5][5], r[5];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> r[i];
    for (int i = 1; i <= m; i++) {
        for (int l = 1; l <= n; l++) {
            for (int r = l; r <= n; r++) {
                cin >> c[i][l][r];
            }
        }
    }
    ll ans = 1e18;
    for (int bits = 0; bits < (1<<n); bits++) {
        ll cost = 0;
        for (int i = 1; i <= n; i++) {
            if (bits&(1<<(i-1))) cost += r[i];
        }
        for (int i = 1; i <= m; i++) {
            vector<ll> dp(5, 1e18);
            dp[0] = 0;
            for (int j = 1; j <= n; j++) {
                if (bits&(1<<(j-1))) {
                    dp[j] = dp[j-1];
                }
                ll best = 1e18;
                for (int l = j; l >= 1; l--) {
                    best = min(best, dp[l-1]);
                    dp[j] = min(dp[j], c[i][l][j] + best);
                }
            }
            cost += dp[n];
        }
        ans = min(ans, cost);
    }
    cout << ans << "\n";
    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 50/50
1 Elfogadva 0/0 3ms 1900 KiB
2 Elfogadva 0/0 3ms 2116 KiB
3 Elfogadva 2/2 119ms 41444 KiB
4 Elfogadva 2/2 3ms 2672 KiB
5 Elfogadva 3/3 4ms 3068 KiB
6 Elfogadva 2/2 20ms 6828 KiB
7 Elfogadva 2/2 202ms 42248 KiB
8 Elfogadva 2/2 196ms 42248 KiB
9 Elfogadva 2/2 200ms 42500 KiB
10 Elfogadva 2/2 202ms 42452 KiB
11 Elfogadva 2/2 201ms 42244 KiB
12 Elfogadva 2/2 180ms 39140 KiB
13 Elfogadva 2/2 188ms 39400 KiB
14 Elfogadva 2/2 61ms 42916 KiB
15 Elfogadva 3/3 68ms 43000 KiB
16 Elfogadva 3/3 115ms 43092 KiB
17 Elfogadva 2/2 115ms 43360 KiB
18 Elfogadva 3/3 116ms 43352 KiB
19 Elfogadva 2/2 184ms 39560 KiB
20 Elfogadva 2/2 193ms 41448 KiB
21 Elfogadva 2/2 201ms 42992 KiB
22 Elfogadva 2/2 202ms 43452 KiB
23 Elfogadva 2/2 202ms 43448 KiB
24 Elfogadva 2/2 202ms 43452 KiB
25 Elfogadva 2/2 209ms 43540 KiB