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();
}
}