Kick Start round E problem Toys editorial

I have implemented 3rd question(Toys) according to analysis section of recent kick start round, thought it might be helpful.

problem and analysis:

Code
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define all(a) a.begin(), a.end()

void solve()
{
    ll n;
    cin >> n;
    vector<ll> e(n), r(n);
    ll sum = 0;

    for (int i = 0; i < n; ++i)
    {
        cin >> e[i] >> r[i];
        sum += e[i];
    }

    ll tsum = sum, mx = sum, rmv_mx = 0, rmv = 0;

    priority_queue<pll> pq;

    for (int i = 0; i < n; ++i)
    {
        tsum += e[i];
        pq.push({e[i] + r[i], r[i]});

        while (!pq.empty() && pq.top().first > sum)
        {
            ++rmv;
            int ee = pq.top().first - pq.top().second;
            sum -= ee;
            tsum -= 2 * ee;
            pq.pop();
        }

        if (tsum > mx)
        {
            mx = tsum;
            rmv_mx = rmv;
        }
    }

    if (pq.size() > 0)
        cout << n - pq.size() << " INDEFINITELY" << endl;
    else
        cout << rmv_mx << " " << mx << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin >> t;
    for (int i = 1; i <= t; ++i)
    {
        cout << "Case #" << i << ": ";
        solve();
    }
}
1 Like

Use 3 back-ticks before and after your code to indent.

1 Like