Submission #4626772

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

const int INF = 0x3f3f3f3f, MOD = 1000000007;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
/*-----------------------------------------*/
int n, m, c[4], cost[4], idol[4][10];
double p[4][10], dp[1 << 10];
double rec(int comp) {
  if (dp[comp] != -1) return dp[comp];
  if (comp == (1 << n) - 1) return dp[comp] = 0;
  dp[comp] = INF;
  REP(i, m) {
    double lhs = 1, rhs = cost[i];
    REP(j, c[i]) {
      if (comp >> idol[i][j] & 1) lhs -= p[i][j];
      else rhs += p[i][j] * rec(comp | 1 << idol[i][j]);
    }
    if (lhs != 0) dp[comp] = min(dp[comp], rhs / lhs);
  }
  return dp[comp];
}

int main() {
  // freopen("input.txt", "r", stdin);

  cin >> n >> m;
  REP(i, m) {
    cin >> c[i] >> cost[i];
    REP(j, c[i]) {
      cin >> idol[i][j] >> p[i][j]; --idol[i][j];
      p[i][j] /= 100;
    }
  }
  REP(i, 1 << n) dp[i] = -1;
  printf("%.10f\n", rec(0));
  return 0;
}

Submission Info

Judge Result