Submission #10379181
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];
}
}
FORD(i, D - 1, 0) {
if (tot >= G) break;
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
Submission Time |
|
Task |
C - All Green |
User |
RunGood |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
2229 Byte |
Status |
WA |
Exec Time |
1 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 300 |
Status |
|
|
Set Name |
Test Cases |
Sample |
a01, a02, a03, a04 |
All |
a01, a02, a03, a04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24 |
Case Name |
Status |
Exec Time |
Memory |
a01 |
AC |
1 ms |
256 KB |
a02 |
WA |
1 ms |
256 KB |
a03 |
AC |
1 ms |
256 KB |
a04 |
AC |
1 ms |
256 KB |
b05 |
WA |
1 ms |
256 KB |
b06 |
WA |
1 ms |
256 KB |
b07 |
AC |
1 ms |
256 KB |
b08 |
AC |
1 ms |
256 KB |
b09 |
AC |
1 ms |
256 KB |
b10 |
AC |
1 ms |
256 KB |
b11 |
AC |
1 ms |
256 KB |
b12 |
AC |
1 ms |
256 KB |
b13 |
AC |
1 ms |
256 KB |
b14 |
AC |
1 ms |
256 KB |
b15 |
AC |
1 ms |
256 KB |
b16 |
AC |
1 ms |
256 KB |
b17 |
AC |
1 ms |
256 KB |
b18 |
AC |
1 ms |
256 KB |
b19 |
AC |
1 ms |
256 KB |
b20 |
AC |
1 ms |
256 KB |
b21 |
AC |
1 ms |
256 KB |
b22 |
AC |
1 ms |
256 KB |
b23 |
AC |
1 ms |
256 KB |
b24 |
AC |
1 ms |
256 KB |