Competitive Programming Solutions

abc189_b - Alcoholic

23 Jan 2021 — Tags: implementation — URL

Linearly test if the $i$th liquor gets Takahashi drunk. To avoid precision errors, multiply $x$ by $100$ instead of dividing each percentage by $100$.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int solve(vi v, vi p, ll x)
{
    int n = (int)(v).size();
    ll cur = 0;
    x *= 100;
    for (int i = 0; i < n; ++i)
    {
        cur += v[i] * p[i];
        if (cur > x)
            return i + 1;
    }
    return -1;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, x;
    cin >> n >> x;
    vi v(n), p(n);
    for (int i = 0; i < n; ++i)
        cin >> v[i] >> p[i];
    cout << solve(v, p, x);
    return 0;
}

Related posts