E - Payment Required
Source: atcoder
Difficulty: 450

Problem Statement
In the year 30XX, each submission to a certain contest requires a payment.
The contest has
N
problems. Problem
i
has
S_i
points, and each submission costs
C_i
yen.
When Takahashi submits to the
i
-th problem, he solves it with probability
P_i
%. Each submission’s outcome is independent of the others.
He has
X
yen. He cannot make any submission that would cause his total spending to exceed
X
yen.
Find the expected value of the total score of the problems he solves when he chooses submissions to maximize this value.
He may decide which problem to submit to next after seeing the result of the previous submission, and solving the same problem more than once awards the same score as solving it once.
Constraints
1 \leq N \leq 8
1 \leq S_i \leq 2718
1 \leq C_i \leq X \leq 5000
1 \leq P_i \leq 100
All input values are integers.
Input
The input is given from Standard Input in the following format:
N
X
S_1
C_1
P_1
S_2
C_2
P_2
\vdots
S_N
C_N
P_N
Output
Print the answer. Your output is considered correct if its absolute or relative error does not exceed
10^{-6}
.
Sample Input 1
3 2
100 1 50
200 1 20
1000 1 1
Sample Output 1
95
Consider the following submission strategy:
First, submit to the 1st problem.
If that submission is correct, submit to the 2nd problem; otherwise, submit again to the 1st problem.
The expected total score for this strategy is
95
points. No strategy can exceed an expected score of
95
, so print
95
.
Sample Input 2
2 7
100 3 50
100 2 50
Sample Output 2
125
Sample Input 3
5 32
500 9 57
300 4 8
300 3 32
300 7 99
100 8 69
Sample Output 3
953.976967020096
Sample Input 4
7 78
100 1 100
200 2 90
300 3 80
400 4 60
450 5 50
525 6 30
650 7 1
Sample Output 4
1976.2441416041121021

C++ solution:
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>

using namespace std;

int main() {
    int N, X;
    cin >> N >> X;

    vector<int> S(N), C(N), P(N);
    for (int i = 0; i < N; ++i) {
        cin >> S[i] >> C[i] >> P[i];
    }

    int max_mask = 1 << N;
    vector<vector<double>> dp(max_mask, vector<double>(X + 1, 0.0));

    for (int mask = max_mask - 1; mask >= 0; --mask) {
        for (int x = 0; x <= X; ++x) {
            double max_exp = 0.0;
            for (int i = 0; i < N; ++i) {
                if (!(mask & (1 << i))) {
                    if (x >= C[i]) {
                        double success_prob = P[i] / 100.0;
                        double fail_prob = 1.0 - success_prob;
                        int new_mask = mask | (1 << i);
                        int remaining_x = x - C[i];
                        double success_value = S[i] + dp[new_mask][remaining_x];
                        double fail_value = dp[mask][remaining_x];
                        double current_exp = success_prob * success_value + fail_prob * fail_value;
                        if (current_exp > max_exp) {
                            max_exp = current_exp;
                        }
                    }
                }
            }
            if (max_exp > dp[mask][x]) {
                dp[mask][x] = max_exp;
            }
        }
    }

    cout << fixed << setprecision(15) << dp[0][X] << endl;

    return 0;
}

Go solution:
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wt = bufio.NewWriter(os.Stdout)
)

const (
	inf = 1 << 60
	MOD = 998244353
)

func main() {
	/*** INIT ***/
	defer wt.Flush()
	sc.Buffer([]byte{}, inf)
	sc.Split(bufio.ScanWords)

	n, x := InputInt(), InputInt()
	s, c, p := make([]float64, n), make([]int, n), make([]float64, n)
	for i := 0; i < n; i++ {
		t1, t2, t3 := InputInt(), InputInt(), InputInt()
		s[i], c[i], p[i] = float64(t1), t2, float64(t3)/100.0
	}

	v := make([]int, n)
	for i := 0; i < n; i++ {
		v[i] = i
	}
	permssize, permsidx := 1, 0
	for i := 2; i <= n; i++ {
		permssize *= i
	}
	perms := make([][]int, permssize)
	for i := 0; i < len(perms); i++ {
		perms[i] = make([]int, len(v))
	}
	PermsGen(perms, v, &permsidx)
	// fmt.Fprintln(wt, perms)

	dp := Slice2dGen(1<<n, x+1)
	for j := 0; j <= x; j++ {
		for i := 0; i < (1 << n); i++ {
			for k := 0; k < n; k++ {
				jj := j - c[k]
				ii := i | (1 << k)
				if jj < 0 || ii == i {
					continue
				}
				val := p[k]*(dp[ii][jj]+s[k]) + (1.0-p[k])*dp[i][jj]
				dp[i][j] = Max(dp[i][j], val)
			}
		}
	}
	fmt.Fprintln(wt, dp[0][x])
}

func Max(a, b float64) float64 {
	if a < b {
		return b
	} else {
		return a
	}
}

func Slice2dGen(h, w int) [][]float64 {
	v := make([][]float64, h)
	for i := range v {
		v[i] = make([]float64, w)
	}
	default_val := 0.0
	for i := 0; i < h; i++ {
		for j := 0; j < w; j++ {
			v[i][j] = default_val
		}
	}
	return v
}

func PermsGen(ret [][]int, v []int, permsidx *int) {
	used, vec := make([]bool, len(v)), make([]int, len(v))
	var rec func(pos int)
	rec = func(pos int) {
		if pos == len(v) {
			for j := 0; j < len(v); j++ {
				ret[*permsidx][j] = vec[j]
			}
			*permsidx++
			return
		}
		for i := range used {
			if used[i] == true {
				continue
			}
			vec[pos] = v[i]
			used[i] = true
			rec(pos + 1)
			used[i] = false
		}
	}
	rec(0)
}

/*** I/O ***/
func InputInt() int {
	sc.Scan()
	val, _ := strconv.Atoi(sc.Text())
	return val
}

func InputString() string {
	sc.Scan()
	return sc.Text()
}

func OutInt(val int) {
	fmt.Fprintln(wt, val)
}

func OutString(s string) {
	fmt.Fprintln(wt, s)
}

Java solution:
import java.util.*;
import java.io.*;
import java.util.function.*;
//雛形
public class Main{
	public static void main(String[] args) {
		FastScanner stdin = new FastScanner(System.in);
		int N = stdin.nextInt();
		int[] pow = new int[N];
		pow[0]=1;
		int sum=1;
		for(int i=1;i<N;i++){
			pow[i]=pow[i-1]*2;
			sum+=pow[i];
		}
		int X = stdin.nextInt();
		double[][] dp = new double[X+1][sum+1];
		double[] S = new double[N];
		int[] C = new int[N];
		double[] p = new double[N];
		for(int i=0;i<N;i++){
			S[i] = stdin.nextDouble();
			C[i] = stdin.nextInt();
			p[i] = stdin.nextDouble()/100.0;
			//System.out.printf("%f,%d,%f\n", S[i],C[i],dp[i][0]);
		}
		stdin.close();
		for(int i=1;i<=X;i++){
			for(int j=1;j<=sum;j++){
				double max = dp[i-1][j];
				for(int k=0;k<N;k++){
					if((j&pow[k])!=0&&i>=C[k]){
						max = Double.max(max, (1.0-p[k])*dp[i-C[k]][j]+p[k]*dp[i-C[k]][j-pow[k]]+p[k]*S[k]);
					}
				}
				dp[i][j]=max;
				//System.out.printf("%d,%d,%f\n", i,j,max);
			}
		}
		System.out.println(dp[X][sum]);
	}
	static void yes_no(boolean flag){
		if(flag){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
	static int keta_num(long k){
		return Math.toIntExact(binary_search(0, 18, (i)->long_pow(10, i)<=k))+1;
	}
	static long long_pow(long a,long k){
		if(k==1){
			return a;
		}else if(k==0){
			return 1;
		}
		long hoge = long_pow(a, k/2);
		long foo = k%2==1?a:1;
		return hoge*hoge*foo;
	}
	//しきい値以下でtrueとなるpredを与えると、閾値を求めてくれる。探索範囲は[a,b)
	//配列のidxに入れるときはlong_to_int
	static long binary_search(long a,long b,Predicate<Long> pred){
		if(!pred.test(a)){
			return a;
		}else if(pred.test(b)){
			return b;
		}
		return binary_search_main(a,b,pred);
	}
	static long binary_search_main(long a,long b,Predicate<Long> pred){
		if(b-a<2){
			boolean now = pred.test(a);
			boolean next = true;
			for(long i=a;i<b;i++){
				next = pred.test(i+1);
				if(now&&!next){
					return i;
				}
				now = next;
			}
			return b;
		}else{
			long t =(a+b)/2;
			if(pred.test(t)){
				return binary_search_main(t, b, pred);
			}else{
				return binary_search_main(a, t, pred);
			}
		}
	}
}

//追加クラスはここに追記



//ここだよーーーーーーー

class FastScanner implements Closeable {
	private final InputStream in;
	private final byte[] buffer = new byte[1024];
	private int ptr = 0;
	private int buflen = 0;
	public FastScanner(InputStream in) {
		this.in = in;
	}
	private boolean hasNextByte() {
		if (ptr < buflen) {
			return true;
		}else{
			ptr = 0;
			try {
				buflen = in.read(buffer);
			} catch (IOException e) {
				e.printStackTrace();
			}
			if (buflen <= 0) {
				return false;
			}
		}
		return true;
	}
	private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
	private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
	public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
	public String next() {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = readByte();
		while(isPrintableChar(b)) {
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	public long nextLong() {
		if (!hasNext()) throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b) {
			throw new NumberFormatException();
		}
		while(true){
			if ('0' <= b && b <= '9') {
				n *= 10;
				n += b - '0';
			}else if(b == -1 || !isPrintableChar(b)){
				return minus ? -n : n;
			}else{
				throw new NumberFormatException();
			}
			b = readByte();
		}
	}
	public int nextInt() {
		long nl = nextLong();
		if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
		return (int) nl;
	}
	public double nextDouble() { return Double.parseDouble(next());}
	public void close() {
		try {
			in.close();
		} catch (IOException e) {
		}
	}
}

JavaScript solution:
function Main(input) {
  input = input.split("\n").map((line) => line.trim());
  const [N, X] = input[0].split(" ").map(Number);
  const [S, C, P] = [[], [], []];
  for (let i = 0; i < N; i++) [S[i], C[i], P[i]] = input[i + 1].split(" ").map(Number);
  const dp = new Array(1 << N).fill(0).map(() => new Array(X + 1).fill(0));
  for (let j = 0; j <= X; j++) {
      for (let i = 0; i < 1 << N; i++) {
      for (let k = 0; k < N; k++) {
        if (i & (1 << k)) continue;
        const ni = i | (1 << k);
        const nj = j + C[k];
        if (nj > X) continue;
        const p = P[k] / 100;
        let success = p * (dp[i][j] + S[k]);
        let fail = (1 - p) * dp[ni][j];
        dp[ni][nj] = Math.max(dp[ni][nj], success + fail);
      }
    }
  }

  let ans = 0;
  for (let i = 0; i < 1 << N; i++) {
    for (let j = 0; j <= X; j++) ans = Math.max(ans, dp[i][j]);
  }
  console.log(ans);
}

Main(require("fs").readFileSync(0, "utf8"));

Python solution:
N, X = map(int, input().split())
S, C, P = [], [], []
for _ in range(N):
  s, c, p = map(int, input().split())
  S.append(s)
  C.append(c)
  P.append(p / 100.0)

M = 1 << N
dp = [[0.0] * (X + 1) for _ in range(M)]
for m in range(1, X + 1):
  for mask in range(M):
    best = 0.0
    for i in range(N):
      if (mask >> i) & 1:
        continue
      if C[i] > m:
        continue
      p = P[i]
      rest = m - C[i]
      solved_mask = mask | (1 << i)
      val = p * (S[i] + dp[solved_mask][rest]) + (1 - p) * dp[mask][rest]
      if val > best:
        best = val
    dp[mask][m] = best

ans = dp[0][X]
out = f"{ans:.15f}".rstrip('0').rstrip('.')
print(out)

Ruby solution:
n, x = gets.chomp.split.map(&:to_i)
tasks = Array.new(n) { gets.chomp.split.map(&:to_i) }
tasks.map! { |s, c, p_| [s, c, p_ / 100.0] }

dp = Array.new(x + 1) { Array.new(1 << n, 0) }
1.upto(x) do |i|
  (1 << n).times do |j|
    n.times do |k|
      # next if j & (1 << k) == 0
      # ni = i + c
      # nj = j ^ (1 << k)
      # dp[ni][nj] += (dp[i][j] + s) * p_
      next if j & (1 << k) > 0
      s, c, p_ = tasks[k]
      ni = i - c
      next if ni < 0
      nj = j | (1 << k)
      dp[i][j] = [dp[i][j], (dp[ni][nj] + s) * p_ + dp[ni][j] * (1 - p_)].max
    end
  end
  # dp.each { |r| p r }
  # puts "-" * 40
end
puts dp[x][0]