Problem:

Auto comment: topic has been updated by beginner_610 (previous revision, new revision, compare).

Auto comment: topic has been updated by beginner_610 (previous revision, new revision, compare).

Auto comment: topic has been updated by beginner_610 (previous revision, new revision, compare).

You can check here, some points may be useful.

This is just a weird variation of IOI Job Processing. Maybe looking at that sol will help you.

Hey I recently came across this question and implemented a solution with time complexity O(xLog(x)+yLog(y)+zLog(z)) so basically the time complexity is nLog(n) where n = max(x,y,z); Ideone Solution Link Feel Free to comment in case you have any doubt.

#include <bits/stdc++.h>
using namespace std;
int main() {
	int test;
	cin>>test;
	while(test--)
	{
		int x,y,z,k,i;
		cin>>x>>y>>z>>k;
		vector<int>vec(y);
		vector<int>printed;
		for(int i=0;i<y;++i)
		cin>>vec[i];
		sort(vec.begin(),vec.end());
		priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
		int currtime = 0;
		i=0;
		int j=0;
		while(i<x)
		{
			if(pq.empty())
			{
			pq.push(make_pair(vec[j],j));
			++j;
			++i;
			}
			else
			{
				if(j<y && pq.top().first>vec[j])
				{
					pq.push(make_pair(vec[j],j));
					++j;
					++i;
				}
				else
				{
					int currtime=pq.top().first;
					int currmachine=pq.top().second;
					printed.push_back(currtime);
					pq.pop();
					pq.push(make_pair(currtime+vec[currmachine],currmachine));
					++i;
				}
			}
		}
		while(!pq.empty())
		{
			printed.push_back(pq.top().first);
			pq.pop();
		}
		i=0;
		vector<int>finalvec;
		for(i=0;i<min((int)printed.size(),z);++i)
			pq.push(make_pair(printed[i]+k,1));
		while(i<printed.size())
		{
			finalvec.push_back(pq.top().first);
			currtime = max(pq.top().first,printed[i]);
			pq.pop();
			pq.push(make_pair(currtime+k,1));
			++i;
		}
		while(!pq.empty())
		{
			finalvec.push_back(pq.top().first);
			pq.pop();
		}
		cout<<"answer is "<<finalvec[finalvec.size()-1]<<endl;
	}
	return 0;
}

Imagine if the question was to calculate if it's possible to publish X books in a given time t, this can be solved by considering all printing machines and binding machines. Now you just have to binary search for the time t

This question can be solved greedily. - In a set(multiset to be specific), the printing finish time will be stored for each printing machine. Initially, all printing machines will be available so if we take any machine its ending time will be the time it takes to print a book. Suppose we take 1st machine with time 5, then if we take it next time its task will end at 10. So, we will replace the finishing time for 1st machine to be 10. - Similar logic is used for binding machine's job.

Here is my code.

#include <bits/stdc++.h>
using namespace std;

using ll = long long int;

void solve() {
	int x, y, z, k;
	cin >> x >> y >> z >> k;
	multiset<pair<ll,ll>> print;
	for(int i=0, t; i<y; i++) {
		cin >> t;
		print.insert({t, t});
	}
	multiset<ll> bound;
	for(int i=0; i<min(x, z); i++)
		bound.insert(0);
	ll ans, cur, t;
	for(int i=0; i<x; i++) {
		cur = print.begin()->first;
		t = print.begin()->second;
		print.erase(print.begin());
		print.insert({cur+t, t});
		ans = max(cur, *bound.begin())+k;
		bound.erase(bound.begin());
		bound.insert(ans);
	}
	cout << ans << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int _t; cin >> _t; while(_t--)
    solve();
}