提出 #65470702

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define REP(a,i,n) for (ll i=a;i<n;i++)

int N, M;
vector<int> ems(200005, 0);
vector<vector<int> > zoos(10, vector<int>(100));
vector<int> costs(10);

ll backtracking(vector<int> &visits, int i=0, ll cost=0) {
    if (i==N) {
        int com=0;
        REP(0, i, M) com += (visits[i]>=2);
        if (com==M) return cost;
        return 1e18;
    }
    ll mCost = backtracking(visits, i+1, cost);
    REP(1, _, 3) {
        REP(0, j, M) {
            visits[j] += _*zoos[i][j];
        }
        cost += costs[i];
        mCost = min(mCost, backtracking(visits, i+1, cost));
        REP(0, j, M) {
            visits[j] -= _*zoos[i][j];
        }
    }
    return mCost;
}

int main() {
    cin >> N >> M;
    REP(0, i, N) cin >> costs[i];
    REP(0, i, M) {
        int K; cin >> K;
        while (K--) {
            int x; cin >> x;
            zoos[x-1][i]=1;
        }
    }
    vector<int> temp(100);
    cout << backtracking(temp);
    return 0;
}

提出情報

ジャッジ結果