Submission #65470713

Source Code Expand

// 不急不急 DFS 小题

#include <bits/stdc++.h>
typedef long long ll;
#define one(x) ((ll)(1e##x))
using namespace std;
typedef pair<int, int> pii;

ll n, m, ans(1000000000ll*10000ll), fin;

ll c[200];

ll k[200], a[200][200];

unordered_set<ll> ini[200];

ll acnt[200];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin>>n>>m;
    for(ll i(1); i<=n; i++) cin>>c[i];
    for(ll i(1); i<=m; i++) {
        cin>>k[i];
        for(ll j(1); j<=k[i]; j++) {
            cin>>a[i][j];
            ini[a[i][j]].insert(i);
        }
    }
    for(ll i(0); i<=(1<<(2*n))-1; i++) {
        ll cost(0);
        fill(acnt+1, acnt+m+1, 0);
        ll j(i), cnt(1);
        while(j) {
            if(j&1) {
                for(auto k : ini[(cnt>n ? cnt-n : cnt)]) acnt[k]++;
                cost+=c[(cnt>n ? cnt-n : cnt)];
            }
            j>>=1;
            cnt++;
        }
        bool f(1);
        for(ll i(1); i<=m; i++) {
            if(acnt[i]<2) {f=0; break; }
        }
        if(f && cost<ans) ans=cost, fin=i;
    }
    cout<<ans;
    return 0;
}

Submission Info

Submission Time
Task D - Goin' to the Zoo
User c_legg
Language C++ 20 (gcc 12.2)
Score 400
Code Size 1132 Byte
Status AC
Exec Time 1651 ms
Memory 3792 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 35
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
All hand_01.txt, hand_02.txt, hand_03.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
hand_01.txt AC 2 ms 3500 KiB
hand_02.txt AC 1 ms 3428 KiB
hand_03.txt AC 1 ms 3444 KiB
random_01.txt AC 1651 ms 3732 KiB
random_02.txt AC 1641 ms 3616 KiB
random_03.txt AC 685 ms 3668 KiB
random_04.txt AC 880 ms 3616 KiB
random_05.txt AC 77 ms 3484 KiB
random_06.txt AC 21 ms 3408 KiB
random_07.txt AC 967 ms 3668 KiB
random_08.txt AC 4 ms 3792 KiB
random_09.txt AC 72 ms 3496 KiB
random_10.txt AC 1 ms 3424 KiB
random_11.txt AC 908 ms 3640 KiB
random_12.txt AC 2 ms 3664 KiB
random_13.txt AC 84 ms 3536 KiB
random_14.txt AC 1 ms 3448 KiB
random_15.txt AC 804 ms 3668 KiB
random_16.txt AC 1 ms 3632 KiB
random_17.txt AC 109 ms 3464 KiB
random_18.txt AC 1 ms 3496 KiB
random_19.txt AC 71 ms 3532 KiB
random_20.txt AC 144 ms 3352 KiB
random_21.txt AC 2 ms 3628 KiB
random_22.txt AC 75 ms 3440 KiB
random_23.txt AC 2 ms 3504 KiB
random_24.txt AC 17 ms 3496 KiB
random_25.txt AC 2 ms 3420 KiB
random_26.txt AC 79 ms 3500 KiB
random_27.txt AC 2 ms 3496 KiB
random_28.txt AC 6 ms 3444 KiB
random_29.txt AC 5 ms 3432 KiB
random_30.txt AC 19 ms 3340 KiB
sample_01.txt AC 1 ms 3412 KiB
sample_02.txt AC 2 ms 3340 KiB