提出 #65455545

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
#define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define INF 0x7fffffff
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long
#define PII pair<int,int>
#define mod 998244353
const int MOD=1e9+7;
const int N=1e5+10;
int read() {char act = 0;int f = 1, x= 0;while (act = getchar(), act < '0' && act != '-');if (act == '-') f = -1, act = getchar();x = act - '0';while (act = getchar(), act >= '0') x = x * 10 + act - '0';return x * f;}
void solve(){
    int N, M;
    cin >> N >> M;
    vector<long long> C(N + 10);
    for (int i = 1; i <= N; i++) {
        cin >> C[i];
    }
    vector<vector<int>> zoo(M);
    for (int i = 0; i < M; i++) {
        int K;
        cin >> K;
        vector<int> list(K);
        for (int j = 0; j < K; j++) {
            cin >> list[j];
        }
        zoo[i] = list;
    }

    long long ans = LLONG_MAX;
    int maxx = 1;
    for (int i = 0; i < N; i++) {
        maxx *= 3;
    }

    for (int mask = 0; mask < maxx; mask++) {
        int x[N + 1] = {0}; // x[1..N]
        long long cost = 0;
        int tmp = mask;
        for (int j = 0; j < N; j++) {
            int cnt = tmp % 3;
            tmp /= 3;
            x[j + 1] = cnt;
            cost += cnt * C[j + 1];
        }

        bool flag = true;
        for (int i = 0; i < M; i++) {
            int sum = 0;
            for (int a : zoo[i]) {
                sum += x[a];
                if (sum >= 2) break;
            }
            if (sum < 2) {
                flag = false;
                break;
            }
        }

        if (flag && cost < ans) {
            ans = cost;
        }
    }

    cout << ans << endl;
}
signed main()
{
    IOS;
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

提出情報

ジャッジ結果