Problem -2 : Ingredient Optimization
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define rep(i, l, r) for ((i) = (l); (i) <=(r); (i)++)
#define rep1(i, r, l) for ((i) = (r); (i) >=(l); (i)--)
bool compare(const pair<ll,ll>&p1, const pair<ll,ll>&p2)
{
if(p1.first < p2.first)
{
return true;
}
if(p1.first == p2.first)
{
return p1.second < p2.second;
}
return false;
}
int main()
{
ios_base::sync_with_stdio(false) ;
cin.tie(NULL);
cout.tie(NULL);
ll t ;ll i1 = 1 ;
cin>>t;
while(t--)
{
ll bad = 0 ;
ll d,n,u ;
cin>>d>>n>>u ;
ll i ;
vector<pair<ll,ll>> w;
map<ll,ll> q,e;
rep(i,1,d){
ll x,y,z ;
cin>>x>>y>>z;
w.push_back({x,0});
q[x] = y; e[x]=z;
}
rep(i,1,n){
ll x ;
cin>>x;
w.push_back({x,1});
}ll r = 0 ;
sort(w.begin(),w.end(),compare);
ll k2 = w.size();
multiset <ll> ok ;
rep(i,0,k2-1){
// cout<<w[i].first<<" "<<w[i].second<<'\n';
if(bad==0){
if(w[i].second==0){
ll current_time = w[i].first ; ll quantity = q[w[i].first];
ll end_time = current_time + e[current_time];ll h = 1 ;
rep(h,1,quantity){ //
ok.insert(end_time);
}
}
else
{
ll k2 = 0 ;
ll sz = ok.size();
if(sz==0){
k2=1;
}
ll count = 0 ;
while(k2==0 && count<u){
ll guy = *ok.begin();
if(guy>w[i].first)
{
ok.erase(ok.find(guy));
count++;
}
else
{
ok.erase(ok.find(guy));
}
sz = ok.size();
if(sz==0){
k2=1;
}
}
// if(store>=u){
// store=store-u;
// r++;
// }
// else{
// bad = 1 ;
// }
if(count==u){
r++;
}
else
{
bad = 1 ;
}
}
}
else
{
}
}
cout<<"Case #";
cout<<i1;cout<<": ";
i1++;
cout<<r;
cout<<'\n';
}
return 0 ;
}