84462024-01-16 15:11:47TuruTamasFestés (50 pont)cpp17Time limit exceeded 22/50702ms46124 KiB
// a kurva anyját ennek a feladatnak, baszódjon meg!

#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<vector<ll>>> vvs;
vector<pair<vvi, ll>> C;
vi R;
vector<ll> s;
vector<ll> festett;
vi Csum;

void f(ll i, vector<vector<ll>> &v) {
    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);
            v.push_back(s);
        }
    }
}

ll g(vector<ll>::iterator it, ll m) {
    if (it == s.end())
        return 0;
    if (find(festett.begin(), festett.end(), *it) != festett.end())
        return g(++it, m);

    ll r = LLONG_MAX;
    for (auto range : vvs[*it]) {
        ll first = *range.begin();
        ll last = *range.rbegin();
        ll to_remove = festett.size();
        for (ll val : range) {
            festett.push_back(val);
        }
        to_remove = festett.size() - to_remove;
        auto nit = it;
        nit++;
        r = min(r, C[m].first[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 sor = 0; sor < N; sor++) {
            if (find(s.begin(), s.end(), sor) == s.end())
                ans_tmp += R[sor];
        }
        for (ll m = 0; m < M; m++) {
            if (ans_tmp >= ans)
                return;
            ans_tmp += g(s.begin(), m);
        }
        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);
    ll ind = 0;
    for (ll m = 0; m < M; m++) {
        C[m].first.resize(N);
        C[m].second = ind++;
        for (ll l = 0; l < N; l++) {
            C[m].first[l].resize(N);
            for (ll r = l; r < N; r++) {
                input >> C[m].first[l][r];
            }
        }
    }
    Csum.assign(C.size(), 0);
    for (ll m = 0; m < M; m++) {
        for (vi &v : C[m].first) {
            Csum[m] += accumulate(v.begin(), v.end(), 0LL);
        }
    }
    sort(C.begin(), C.end(), [](pair<vvi, ll> &lhs, pair<vvi, ll> &rhs) {
        return Csum[lhs.second] > Csum[rhs.second];
    });

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

    call_g(0);
    cout << ans << "\n";
}
SubtaskSumTestVerdictTimeMemory
base22/50
1Accepted0/03ms2072 KiB
2Accepted0/03ms2112 KiB
3Accepted2/2462ms44324 KiB
4Accepted2/24ms2664 KiB
5Accepted3/314ms3432 KiB
6Accepted2/2135ms9576 KiB
7Time limit exceeded0/2666ms36084 KiB
8Time limit exceeded0/2643ms36168 KiB
9Time limit exceeded0/2663ms36024 KiB
10Time limit exceeded0/2663ms36244 KiB
11Time limit exceeded0/2663ms36168 KiB
12Time limit exceeded0/2676ms33552 KiB
13Time limit exceeded0/2657ms33808 KiB
14Accepted2/2178ms36504 KiB
15Accepted3/3194ms36500 KiB
16Accepted3/3349ms46004 KiB
17Accepted2/2310ms46088 KiB
18Accepted3/3465ms46124 KiB
19Time limit exceeded0/2657ms33660 KiB
20Time limit exceeded0/2657ms35380 KiB
21Time limit exceeded0/2662ms36864 KiB
22Time limit exceeded0/2663ms37172 KiB
23Time limit exceeded0/2681ms37396 KiB
24Time limit exceeded0/2702ms37356 KiB
25Time limit exceeded0/2648ms37572 KiB