Submission #44529764

---

Source Code Expand

#pragma GCC optimize ("O3")

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

using ll = long long; 
using ld = long double; 
using str = string; 

using pii = pair<int, int>; 
using pll = pair<ll, ll>; 
#define mp make_pair
#define fs first 
#define sc second

using ull = unsigned long long; 
using mii = map<int, int>; 
using mll = map<ll, ll>; 
#define fd(x, e) (x.find(e) != x.end())

#define tcT template <class T
#define tcTU tcT, class U
#define vt vector //tcT > using vt = vector<T>;
#define ar array // tcT, size_t SZ > using ar = array<T, SZ>;
using vi = vt<int>;
using vb = vt<bool>;
using vl = vt<ll>;
using vd = vt<ld>;
using vs = vt<str>;
using vii = vt<pii>;
using vll = vt<pll>;

#define sz(x) int((x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sor(x) sort(x.begin(), x.end()) 
#define rsz resize
#define ins insert
#define pb push_back
#define eb emplace_back
#define ft front()
#define bk back()

#define ts to_string

#define ub upper_bound
#define lb lower_bound
tcT> int lwb(vt<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); }
tcT> int upb(vt<T> &a, const T &b) { return int(ub(all(a), b) - bg(a)); }

#define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
#define rp2(i, a, e) for (int (i) = (a); (i) < (int) (e); (i)+=1)
#define rp3(i, a, e, s) for (int (i) = (a); (i) < (int) (e); (i)+=(s))
#define	rpr(i, e) for (int (i) = (e) - 1; i > -1; (i)-=1)
#define rp4(i, a, e) for (int (i) = a; (i) > (int) (e); (i)-=1)
#define rp5(i, a, e, s) for (int (i) = a; (i) > (int) (e); (i)+=(s))
#define rep(x, a) for (auto & x: a) 

#define quick ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const ld PI = acos((ld)-1);
const int dx4[4]{1, 0, -1, 0}, dy4[4]{0, 1, 0, -1}; // for every grid problem!!
tcT> using pqg = priority_queue<T, vector<T>, greater<T>>;

constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr ll pctll(ll x) { return __builtin_popcountll(x); } 
constexpr int bits(
	int x) { // assert(x >= 0); 
	return x == 0 ? 0 : 31 - __builtin_clz(x);
} // floor(log2(x))
// constexpr int p2(int x) { return 1 << x; }
// constexpr int msk2(int x) { return p2(x) - 1; }

// ------ ------ ------ IO ------ ------ ------ //
template <class A> void re(vt<A>& v);
template <class A, size_t S> void re(array<A, S>& a);

tcT> void re(T& x) { 
	cin >> x;
}
void re(double& d) { 
	string t; 
	re(t); 
	d=stod(t); 
}
void re(long double& d) { 
	string t; 
	re(t); 
	d=stold(t); 
}
tcT> void re(pair<T, T> & p) { 
	T a, b; 
	re(a); 
	re(b); 
	p=make_pair(a, b); 
}
template<class H, class... T> void re(H& h, T&... t) {
	re(h); 
	re(t...); 
}
template<class A> void re(vt<A>& x) { 
	for (auto &a: x) re(a); 
}
template<class A, size_t S> void re(array<A, S>& x) { 
	for (auto &a: x) re(a); 
}
string to_string(char c) { 
	return string(1, c); 
}
string to_string(bool b) { 
	return b?"YES":"NO";
}
string to_string(const char* s) { 
	return string(s); }
string to_string(string s) { 
	return s; 
}
string to_string(vt<bool> v) { 
	string res; 
	rp(i, sz(v)) 
		res+=char('0'+v[i]);  
	return res; 
}
template<size_t S> string to_string(bitset<S> b) { 
	string res; 
	rp(i, S)
		res+=char('0'+b[i]);
	return res; 
}
tcT> string to_string(pair<T, T> p) { 
	string res;
	res += to_string(p.first); 
	res += ' '; 
	res += to_string(p.second); 
	return res;
}
tcT> string to_string(vt<T> & v) { 
	bool f=1; 
	string res; 
	for (auto& x: v) { 
		if(!f) 
			res+=' ';
		f=0; 
		res+=to_string(x);
	} 
	return res;
}
template<class A> void write(A x) { 
	cout << to_string(x); 
}
template<class H, class... T> void write(const H& h, const T&... t) { 
	write(h); 
	write(t...); 
}
void print() { 
	write("\n");
}
template<class H, class... T> void print(const H& h, const T&... t) { 
	write(h); 
	if(sizeof...(t)) 
		write(' '); 
	print(t...);
}
void DBG() {
	cerr << "]" << endl;
}
template<class H, class... T> void DBG(H h, T... t) {
	cerr << to_string(h);
	if(sizeof...(t))
		cerr << ", ";
	DBG(t...);
}
#define wr write
#define ps print
// ------ ------ ------ alg ------ ------ ------ //
tcTU> void sort(vt<T> & a, U f) { 
	sort(a.begin(), a.end(), f); 
}
tcT> void rsor(vt<T> & a) { 
	sort(a.begin(), a.end(), greater<T>()); 
}
void rsor(str & a) { 
	sort(a.begin(), a.end(), greater<char>()); 
}
tcT> void rev(vt<T> & a){ 
	reverse(a.begin(), a.end()); 
}
void rev(str & a){ 
	reverse(a.begin(), a.end()); 
}

#define vmax(x) *max_element(begin(x), end(x))
#define vmin(x) *min_element(begin(x), end(x))
#define umax(x, n) *max_element((x), (x) + (n))
#define umin(x, n) *min_element((x), (x) + (n))

tcT> bool amin(T & a, const T & b) {
	return b<a?a=b, 1:0;
}

tcT> bool amax(T & a, const T & b) {
	return a<b?a=b, 1:0;
}

tcT> T cdiv(T a, T b) {return (a+b-1)/b;} 
 
tcTU> T ftrue(T lo, T hi, U f) { 
	while (lo < hi) { T mid = lo+(hi-lo)/2; f(mid) ? hi = mid : lo = mid+1; } 
	return lo;
}
tcTU> T ltrue(T lo, T hi, U f) {
	while (lo < hi) { T mid = lo+(hi-lo+1)/2; f(mid) ? lo = mid : hi = mid-1; } 
	return lo;
}

#define ri(...) int __VA_ARGS__; re(__VA_ARGS__);
#define rl(...) ll __VA_ARGS__; re(__VA_ARGS__);
#define rs(...) str __VA_ARGS__; re(__VA_ARGS__);

const int mxn = 2e5 + 10; 
const int inf = 1e9 + 10; 
const int M = 998244353;

void solve() {
	ri(n, m); 
	vt<vi> a(n); 
	vi c(n);
	rp(i, n) {
		re(c[i]); 
		ri(x); 
		a[i] = vi(x); 
		re(a[i]); 
	}

	vt<ld> dp(2 * m + 1, (ld)0L); 
	rp(i, m) {
		dp[i] = (ld)9e18L; 
	} 

	rpr(i, m) {
		rp(j, sz(a)) {
			ld sum = 0; 
			ld prob = 0; 
			int siz = sz(a[j]); 
			rp(k, siz) {
				if (a[j][k] == 0) {
					prob += (ld) (1L / ((ld)siz)); 
				} else {
					sum += (ld) ((ld)dp[i+a[j][k]] / ((ld)siz)); 
				}
			}
			// ps("?", j, c[j], sum, prob); 
			amin(dp[i], (ld) (sum + (ld) c[j]) / ((ld) 1L - prob)); 
		}
		// cout << "! " << i << ' ' << dp[i] << "\n";
	}
	cout << fixed << setprecision(30) << dp[0] << "\n";
}

int main() {
	quick; 

	int t = 1; 
	// re(t); 
	while (t--) solve(); 

	return 0; 
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */

 

Submission Info

Compile Error

Main.cpp: In function ‘std::string to_string(std::vector<bool>)’:
Main.cpp:51:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^~~
Main.cpp:120:9: note: in expansion of macro ‘rp’
  120 |         rp(i, sz(v))
      |         ^~
Main.cpp:51:27: note: remove parentheses
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^~~
Main.cpp:120:9: note: in expansion of macro ‘rp’
  120 |         rp(i, sz(v))
      |         ^~
Main.cpp: In function ‘std::string to_string(std::bitset<_Nb>)’:
Main.cpp:51:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^~~
Main.cpp:126:9: note: in expansion of macro ‘rp’
  126 |         rp(i, S)
      |         ^~
Main.cpp:51:27: note: remove parentheses
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^~~
Main.cpp:126:9: note: in expansion of macro ‘rp’
  126 |         rp(i, S)
      |         ^~
Main.cpp: In function ‘void solve()’:
Main.cpp:51:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^~~
Main.cpp:228:9: note: in expansion of macro ‘rp’
  228 |         rp(i, n) {
      |         ^~
Main.cpp:51:27: note: remove parentheses
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^~~
Main.cpp:228:9: note: in expansion of macro ‘rp’
  228 |         rp(i, n) {
      |         ^~
Main.cpp:51:27: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^~~
Main.cpp:236:9: note: in expansion of macro ‘rp’
  236 |         rp(i, m) {
      |         ^~
Main.cpp:51:27: note: remove parentheses
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^~~
Main.cpp:236:9: note: in expansion of macro ‘rp’
  236 |         rp(i, m) {
      |         ^~
Main.cpp:54:28: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
   54 | #define rpr(i, e) for (int (i) = (e) - 1; i > -1; (i)-=1)
      |                            ^~~
Main.cpp:240:9: note: in expansion of macro ‘rpr’
  240 |         rpr(i, m) {
      |         ^~~
Main.cpp:54:28: note: remove parentheses
   54 | #define rpr(i, e) for (int (i) = (e) - 1; i > -1; (i)-=1)
      |                            ^~~
Main.cpp:240:9: note: in expansion of macro ‘rpr’
  240 |         rpr(i, m) {
      |         ^~~
Main.cpp:51:27: warning: unnecessary parentheses in declaration of ‘j’ [-Wparentheses]
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^~~
Main.cpp:241:17: note: in expansion of macro ‘rp’
  241 |                 rp(j, sz(a)) {
      |                 ^~
Main.cpp:51:27: note: remove parentheses
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^~~
Main.cpp:241:17: note: in expansion of macro ‘rp’
  241 |                 rp(j, sz(a)) {
      |                 ^~
Main.cpp:51:27: warning: unnecessary parentheses in declaration of ‘k’ [-Wparentheses]
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^~~
Main.cpp:245:25: note: in expansion of macro ‘rp’
  245 |                         rp(k, siz) {
      |                         ^~
Main.cpp:51:27: note: remove parentheses
   51 | #define rp(i, e) for (int (i) = 0; (i) < (int) (e); (i)+=1)
      |                           ^~~
Main.cpp:245:25: note: in expansion of macro ‘rp’
  245 |                         rp(k, siz) {
      |                         ^~

Judge Result