83542024-01-14 23:32:28TuruTamasFestés (50 pont)cpp17Futási hiba 0/50157ms67796 KiB
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
ifstream in_file("minta/be1.txt");
#define input in_file
#define INTHENAMEOFGOD
#else
#define input cin
#define INTHENAMEOFGOD \
    ios::sync_with_stdio(0); \
    cin.tie(0); \
    cout.tie(0);
#endif
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef array<ll, 2> pii;

ll N, M, a, ans = LLONG_MAX;

vector<vector<ll>> f(ll i) {
    vector<vector<ll>> ret;
    for (ll l = 0; l <= i; l++) {
        for (ll r = i; r < N; r++) {
            vector<ll> s;
            for (ll i = l; i <= r; i++)
                s.push_back(i);
            ret.push_back(s);
        }
    }
    return ret;
}

vector<vector<vector<ll>>> vvs;
vector<vvi> C;
vi R;
vector<ll> s;
vector<ll> festett;

ll g(vector<ll>::iterator it, ll m) {
    if (it == s.end())
        return 0;
    if (count(festett.begin(), festett.end(), *it))
        return g(++it, m);
    
    ll r = LLONG_MAX;
    for (auto range : vvs[*it]) {
        ll first = *range.begin();
        ll last = *range.rbegin();
        ll to_remove;
        for (ll val : range) {
            if (!count(festett.begin(), festett.end(), val)) {
                festett.push_back(val);
                to_remove++;
            }
        }
        auto nit = it;
        nit++;
        r = min(r, C[m][first][last] + g(nit, m));
        for (ll i = 0; i < to_remove; i++)
            festett.pop_back();
    }
    return r;
}

void call_g(ll i) {
    if (i == N) {
        ll ans_tmp = 0;
        for (ll m = 0; m < M; m++) {
            ans_tmp += g(s.begin(), m);
        }
        for (ll sor = 0; sor < N; sor++) {
            if (!count(s.begin(), s.end(), sor))
                ans_tmp += R[sor];
        }
        ans = min(ans, ans_tmp);
    } else {
        call_g(i+1);
        s.push_back(i);
        call_g(i+1);
        s.pop_back();
    }
}

int main() {
    INTHENAMEOFGOD
    input >> N >> M;

    R.resize(N);
    for (ll &val : R)
        input >> val;

    C.resize(M);
    for (ll m = 0; m < M; m++) {
        C[m].resize(N);
        for (ll l = 0; l < N; l++) {
            C[m][l].resize(N);
            for (ll r = l; r < N; r++) {
                input >> C[m][l][r];
            }
        }
    }

    vvs.resize(N);
    for (ll n = 0; n < N; n++) {
        vvs[n] = f(n);
    }

    call_g(0);
    cout << ans << "\n";
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base0/50
1Futási hiba0/03ms1928 KiB
2Futási hiba0/03ms2260 KiB
3Futási hiba0/2104ms41476 KiB
4Futási hiba0/23ms2508 KiB
5Futási hiba0/34ms3240 KiB
6Futási hiba0/217ms9292 KiB
7Futási hiba0/2148ms66924 KiB
8Futási hiba0/2149ms66920 KiB
9Futási hiba0/2153ms67112 KiB
10Futási hiba0/2150ms67124 KiB
11Futási hiba0/2148ms66964 KiB
12Futási hiba0/2136ms61824 KiB
13Futási hiba0/2151ms62196 KiB
14Futási hiba0/259ms33172 KiB
15Futási hiba0/361ms33288 KiB
16Futási hiba0/396ms42492 KiB
17Futási hiba0/294ms42616 KiB
18Futási hiba0/394ms42752 KiB
19Futási hiba0/2136ms61268 KiB
20Futási hiba0/2143ms64536 KiB
21Futási hiba0/2151ms67116 KiB
22Futási hiba0/2150ms67796 KiB
23Futási hiba0/2149ms67724 KiB
24Futási hiba0/2150ms67728 KiB
25Futási hiba0/2157ms67736 KiB