Submission #1070280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070280		Ahmed57	Two Dishes (JOI19_dishes)	C++17	100 / 100	2896 ms	242440 KiB

dishes

#include "bits/stdc++.h"
 
using namespace std;
#define int long long
vector<pair<int,int>> lol[1000001];
int arr1[1000001] = {0};
int arr2[1000001] = {0};
int a[1000001];int s[1000001];int p[1000001];
int b[1000001];int t[1000001];int q[1000001];
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i = 1;i<=n;i++){
		cin>>a[i]>>s[i]>>p[i];
		arr1[i] = a[i]+arr1[i-1];
	}
	for(int i = 1;i<=m;i++){
		cin>>b[i]>>t[i]>>q[i];
		arr2[i] = b[i]+arr2[i-1];
	}
	for(int i = 1;i<=n;i++){
		int l = 0 , r = m , ans = -1;
		while(l<=r){
			int mid = (l+r)/2;
			if(arr2[mid]+arr1[i]<=s[i]){
				ans = mid;l = mid+1;
			}else r = mid-1;
		}
		if(ans==-1)continue;
		lol[ans].push_back({i,p[i]});
	}
	long long all = 0;
	for(int i = 1;i<=m;i++){
		int l = 0 , r = n , ans = -1;
		while(l<=r){
			int mid = (l+r)/2;
			if(arr2[i]+arr1[mid]<=t[i]){
				ans = mid;l = mid+1;
			}else r = mid-1;
		}
		if(ans==-1)continue;
		if(ans!=n)lol[i-1].push_back({ans+1,-q[i]});
		all+=q[i];
	}
	map<int,int> mp;
	for(int i = 0;i<=m;i++){
        sort(lol[i].begin(),lol[i].end());
        reverse(lol[i].begin(),lol[i].end());
		for(auto j:lol[i]){
			if(j.second>=0||i==m){
				mp[j.first]+=j.second;
                continue;
			}
			int ans = j.second;
			auto it = mp.lower_bound(j.first);
			while(it!=mp.end()){
				if(ans+(*it).second>=0){
					mp[(*it).first]+=ans;
					ans = 0;
					break;
				}
				ans+=(*it).second;
				it = mp.erase(it);
			}
		}
	}
	for(auto i:mp)all+=i.second;
	cout<<all<<endl;
}

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9