提出 #65483172

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main() {
  // 入力を受け取る
  int N, M;
  cin >> N >> M;
  vector<ll> C(N), K(M);
  vector<vector<int>> A(M);
  for(int i = 0; i < N; i++) {
    cin >> C[i];
  }
  for(int i = 0; i < M; i++) {
    cin >> K[i];
    A[i].resize(K[i]);
    for(int j = 0; j < K[i]; j++) {
      cin >> A[i][j];
    }
  }

  // can_see[i] := (動物園 i で見ることができる動物のリスト)
  vector<vector<int>> can_see(N);
  for(int i = 0; i < M; i++) {
    for(int j = 0; j < K[i]; j++) {
      can_see[A[i][j] - 1].push_back(i);
    }
  }

  // 0, 1, 2 からなる長さ N 以下の列を探索する
  // v := (長さがちょうど　N の列を列挙したもの)
  vector<int> X(N);
  vector<vector<int>> v;
  auto dfs = [&](auto dfs, int i) -> void {
    if(i == N) {
      v.push_back(X);
    }else {
      for(int x = 0; x <= 2; x++) {
        X[i] = x;
        dfs(dfs, i + 1);
      }
    }
  };
  dfs(dfs, 0);

  // 答えを計算する
  // cnt_vis[i] := (動物園 i を訪れた回数)
  // cnt_see[i] := (動物 i を見た回数)
  ll ans = 2'000'000'000'0;
  for(vector<int> cnt_vis : v) {
    ll cost = 0;
    vector<int> cnt_see(M);
    for(int i = 0; i < N; i++) {
      cost += C[i] * cnt_vis[i];
      for(int animal : can_see[i]) {
        cnt_see[animal] += cnt_vis[i];
      }
    }
    bool ok = true;
    for(int i = 0; i < M; i++) {
      if(cnt_see[i] < 2) ok = false;
    }
    if(ok) ans = min(ans, cost);
  }

  cout << ans << endl;
}

提出情報

ジャッジ結果