Submission #10379118

---

Source Code Expand

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

#define pb push_back
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<=_b;++i)
#define FORD(i,a,b) for(int i=(a),_b=(b);i>=_b;--i)
#define trav(a, x) for (auto& a : x)
using ull = uint64_t;
using ll = int64_t;
using PII = pair<int, int>;
using VI = vector<int>;
#define INF (1ll<<60)

string to_string(string s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }
string to_string(bool b) { return (b ? "true" : "false"); }
template <typename A, typename B> string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; }
template <typename A> string to_string(A v) {
bool first = true; string res = "{";
for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); }
res += "}"; return res; }
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H); debug_out(T...); }
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int D;
    ll G;
    cin >> D >> G;
    vector<ll> P(D + 2), C(D + 2);
    REP(i, D) {
        cin >> P[i] >> C[i];
    }
    int ans = INT_MAX;
    REP(subset, 1 << D) {
        ll tot = 0;
        int probs = 0;
        REP(i, D) {
            if (subset & (1 << i)) {
                tot += P[i] * (i + 1) * 100 + C[i];
                probs += P[i];
            }
        }
        while (tot < G) {
            FORD(i, D - 1, 0) {
                if (subset & (1 << i)) continue;
                ll k = G - tot;
                int left = P[i] - 1;
                int todo = k / (100 * (i + 1));
                todo += (k % (100 * (i + 1))) > 0;
                if (todo <= left) {
                    probs += todo;
                    goto done;
                }
                probs += left;
                tot += left * 100 * (i + 1);
            }
        }
        done:
        ans = min(ans, probs);
    }
    cout << ans << '\n';


}

Submission Info

Judge Result