Roller coaster

#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef __int128 L;

int n;
vector<L> P, R, A, F;

bool ok(L x, int mask) {
  L s = x, pw = 1;
  for (int i = 0; i < n; i++) {
    L need = (mask >> i & 1) ? max(P[i], R[i]) : R[i];
    if (s < need * pw) return false;
    pw *= 100;
    s = s * (100 - F[i]) - A[i] * pw;
  }
  return true;
}

int main() {
  cin >> n;
  P.resize(n); R.resize(n); A.resize(n); F.resize(n);
  for (int i = 0; i < n; i++) {
    long long p, r, a, f;
    cin >> p >> r >> a >> f;
    P[i] = p; R[i] = r; A[i] = a; F[i] = f;
  }
  L best = -1;
  for (int mask = 0; mask < (1 << n); mask++) {
    if (2 * __builtin_popcount(mask) < n) continue;
    L hi = 1;
    while (!ok(hi, mask)) hi *= 2;
    L lo = -1;
    while (hi - lo > 1) {
      L m = (lo + hi) / 2;
      if (ok(m, mask)) hi = m; else lo = m;
    }
    if (best < 0 || hi < best) best = hi;
  }
  string out;
  do { out = char('0' + best % 10) + out; best /= 10; } while (best > 0);
  cout << out << "\n";
  return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED