Submission #1070246

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1070246	2024-08-22T12:26:57 Z	Ahmed57	Two Dishes (JOI19_dishes)	C++17	74 / 100	2696 ms	224712 KB

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++){
		for(auto j:lol[i]){
			if(j.second>=0){
				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.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	391 ms	59988 KB	Output is correct
2	Correct	415 ms	70344 KB	Output is correct
3	Correct	398 ms	66488 KB	Output is correct
4	Correct	385 ms	56616 KB	Output is correct
5	Correct	6 ms	34904 KB	Output is correct
6	Correct	394 ms	62148 KB	Output is correct
7	Correct	181 ms	43700 KB	Output is correct
8	Correct	211 ms	57436 KB	Output is correct
9	Correct	406 ms	66488 KB	Output is correct
10	Correct	268 ms	60108 KB	Output is correct
11	Correct	279 ms	66228 KB	Output is correct

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	34904 KB	Output is correct
2	Correct	5 ms	34904 KB	Output is correct
3	Correct	7 ms	34908 KB	Output is correct
4	Correct	5 ms	34908 KB	Output is correct
5	Correct	5 ms	35016 KB	Output is correct
6	Correct	6 ms	34904 KB	Output is correct
7	Correct	5 ms	34908 KB	Output is correct
8	Correct	6 ms	34908 KB	Output is correct
9	Correct	6 ms	34908 KB	Output is correct
10	Correct	5 ms	34908 KB	Output is correct
11	Correct	6 ms	34908 KB	Output is correct
12	Correct	6 ms	34908 KB	Output is correct
13	Correct	6 ms	34908 KB	Output is correct
14	Correct	6 ms	34908 KB	Output is correct
15	Correct	5 ms	34908 KB	Output is correct
16	Correct	5 ms	34908 KB	Output is correct

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	34904 KB	Output is correct
2	Correct	5 ms	34904 KB	Output is correct
3	Correct	7 ms	34908 KB	Output is correct
4	Correct	5 ms	34908 KB	Output is correct
5	Correct	5 ms	35016 KB	Output is correct
6	Correct	6 ms	34904 KB	Output is correct
7	Correct	5 ms	34908 KB	Output is correct
8	Correct	6 ms	34908 KB	Output is correct
9	Correct	6 ms	34908 KB	Output is correct
10	Correct	5 ms	34908 KB	Output is correct
11	Correct	6 ms	34908 KB	Output is correct
12	Correct	6 ms	34908 KB	Output is correct
13	Correct	6 ms	34908 KB	Output is correct
14	Correct	6 ms	34908 KB	Output is correct
15	Correct	5 ms	34908 KB	Output is correct
16	Correct	5 ms	34908 KB	Output is correct
17	Correct	9 ms	35164 KB	Output is correct
18	Correct	8 ms	35120 KB	Output is correct
19	Correct	10 ms	35160 KB	Output is correct
20	Correct	8 ms	35016 KB	Output is correct
21	Correct	9 ms	35164 KB	Output is correct
22	Correct	8 ms	35164 KB	Output is correct
23	Correct	9 ms	35160 KB	Output is correct

Subtask #4
39.0 / 39.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	34904 KB	Output is correct
2	Correct	5 ms	34904 KB	Output is correct
3	Correct	7 ms	34908 KB	Output is correct
4	Correct	5 ms	34908 KB	Output is correct
5	Correct	5 ms	35016 KB	Output is correct
6	Correct	6 ms	34904 KB	Output is correct
7	Correct	5 ms	34908 KB	Output is correct
8	Correct	6 ms	34908 KB	Output is correct
9	Correct	6 ms	34908 KB	Output is correct
10	Correct	5 ms	34908 KB	Output is correct
11	Correct	6 ms	34908 KB	Output is correct
12	Correct	6 ms	34908 KB	Output is correct
13	Correct	6 ms	34908 KB	Output is correct
14	Correct	6 ms	34908 KB	Output is correct
15	Correct	5 ms	34908 KB	Output is correct
16	Correct	5 ms	34908 KB	Output is correct
17	Correct	9 ms	35164 KB	Output is correct
18	Correct	8 ms	35120 KB	Output is correct
19	Correct	10 ms	35160 KB	Output is correct
20	Correct	8 ms	35016 KB	Output is correct
21	Correct	9 ms	35164 KB	Output is correct
22	Correct	8 ms	35164 KB	Output is correct
23	Correct	9 ms	35160 KB	Output is correct
24	Correct	348 ms	66240 KB	Output is correct
25	Correct	325 ms	64728 KB	Output is correct
26	Correct	355 ms	69560 KB	Output is correct
27	Correct	326 ms	64700 KB	Output is correct
28	Correct	352 ms	63412 KB	Output is correct
29	Correct	328 ms	66228 KB	Output is correct
30	Correct	418 ms	61008 KB	Output is correct
31	Correct	152 ms	46780 KB	Output is correct
32	Correct	180 ms	57604 KB	Output is correct
33	Correct	350 ms	56144 KB	Output is correct
34	Correct	388 ms	67780 KB	Output is correct
35	Correct	291 ms	61012 KB	Output is correct
36	Correct	288 ms	61012 KB	Output is correct

Subtask #5
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	34904 KB	Output is correct
2	Correct	5 ms	34904 KB	Output is correct
3	Correct	7 ms	34908 KB	Output is correct
4	Correct	5 ms	34908 KB	Output is correct
5	Correct	5 ms	35016 KB	Output is correct
6	Correct	6 ms	34904 KB	Output is correct
7	Correct	5 ms	34908 KB	Output is correct
8	Correct	6 ms	34908 KB	Output is correct
9	Correct	6 ms	34908 KB	Output is correct
10	Correct	5 ms	34908 KB	Output is correct
11	Correct	6 ms	34908 KB	Output is correct
12	Correct	6 ms	34908 KB	Output is correct
13	Correct	6 ms	34908 KB	Output is correct
14	Correct	6 ms	34908 KB	Output is correct
15	Correct	5 ms	34908 KB	Output is correct
16	Correct	5 ms	34908 KB	Output is correct
17	Correct	9 ms	35164 KB	Output is correct
18	Correct	8 ms	35120 KB	Output is correct
19	Correct	10 ms	35160 KB	Output is correct
20	Correct	8 ms	35016 KB	Output is correct
21	Correct	9 ms	35164 KB	Output is correct
22	Correct	8 ms	35164 KB	Output is correct
23	Correct	9 ms	35160 KB	Output is correct
24	Correct	348 ms	66240 KB	Output is correct
25	Correct	325 ms	64728 KB	Output is correct
26	Correct	355 ms	69560 KB	Output is correct
27	Correct	326 ms	64700 KB	Output is correct
28	Correct	352 ms	63412 KB	Output is correct
29	Correct	328 ms	66228 KB	Output is correct
30	Correct	418 ms	61008 KB	Output is correct
31	Correct	152 ms	46780 KB	Output is correct
32	Correct	180 ms	57604 KB	Output is correct
33	Correct	350 ms	56144 KB	Output is correct
34	Correct	388 ms	67780 KB	Output is correct
35	Correct	291 ms	61012 KB	Output is correct
36	Correct	288 ms	61012 KB	Output is correct
37	Correct	456 ms	69440 KB	Output is correct
38	Correct	395 ms	64704 KB	Output is correct
39	Correct	346 ms	60064 KB	Output is correct
40	Correct	406 ms	72532 KB	Output is correct
41	Correct	7 ms	34996 KB	Output is correct
42	Correct	520 ms	60944 KB	Output is correct
43	Correct	415 ms	56140 KB	Output is correct
44	Correct	465 ms	67836 KB	Output is correct
45	Correct	383 ms	60868 KB	Output is correct

Subtask #6
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	34904 KB	Output is correct
2	Correct	5 ms	34904 KB	Output is correct
3	Correct	7 ms	34908 KB	Output is correct
4	Correct	5 ms	34908 KB	Output is correct
5	Correct	5 ms	35016 KB	Output is correct
6	Correct	6 ms	34904 KB	Output is correct
7	Correct	5 ms	34908 KB	Output is correct
8	Correct	6 ms	34908 KB	Output is correct
9	Correct	6 ms	34908 KB	Output is correct
10	Correct	5 ms	34908 KB	Output is correct
11	Correct	6 ms	34908 KB	Output is correct
12	Correct	6 ms	34908 KB	Output is correct
13	Correct	6 ms	34908 KB	Output is correct
14	Correct	6 ms	34908 KB	Output is correct
15	Correct	5 ms	34908 KB	Output is correct
16	Correct	5 ms	34908 KB	Output is correct
17	Correct	9 ms	35164 KB	Output is correct
18	Correct	8 ms	35120 KB	Output is correct
19	Correct	10 ms	35160 KB	Output is correct
20	Correct	8 ms	35016 KB	Output is correct
21	Correct	9 ms	35164 KB	Output is correct
22	Correct	8 ms	35164 KB	Output is correct
23	Correct	9 ms	35160 KB	Output is correct
24	Correct	348 ms	66240 KB	Output is correct
25	Correct	325 ms	64728 KB	Output is correct
26	Correct	355 ms	69560 KB	Output is correct
27	Correct	326 ms	64700 KB	Output is correct
28	Correct	352 ms	63412 KB	Output is correct
29	Correct	328 ms	66228 KB	Output is correct
30	Correct	418 ms	61008 KB	Output is correct
31	Correct	152 ms	46780 KB	Output is correct
32	Correct	180 ms	57604 KB	Output is correct
33	Correct	350 ms	56144 KB	Output is correct
34	Correct	388 ms	67780 KB	Output is correct
35	Correct	291 ms	61012 KB	Output is correct
36	Correct	288 ms	61012 KB	Output is correct
37	Correct	456 ms	69440 KB	Output is correct
38	Correct	395 ms	64704 KB	Output is correct
39	Correct	346 ms	60064 KB	Output is correct
40	Correct	406 ms	72532 KB	Output is correct
41	Correct	7 ms	34996 KB	Output is correct
42	Correct	520 ms	60944 KB	Output is correct
43	Correct	415 ms	56140 KB	Output is correct
44	Correct	465 ms	67836 KB	Output is correct
45	Correct	383 ms	60868 KB	Output is correct
46	Correct	2138 ms	180228 KB	Output is correct
47	Correct	2005 ms	156760 KB	Output is correct
48	Correct	1735 ms	154260 KB	Output is correct
49	Correct	2152 ms	224712 KB	Output is correct
50	Correct	2696 ms	172748 KB	Output is correct
51	Correct	2141 ms	146604 KB	Output is correct
52	Correct	2519 ms	206348 KB	Output is correct
53	Correct	2017 ms	156816 KB	Output is correct

Subtask #7
0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	391 ms	59988 KB	Output is correct
2	Correct	415 ms	70344 KB	Output is correct
3	Correct	398 ms	66488 KB	Output is correct
4	Correct	385 ms	56616 KB	Output is correct
5	Correct	6 ms	34904 KB	Output is correct
6	Correct	394 ms	62148 KB	Output is correct
7	Correct	181 ms	43700 KB	Output is correct
8	Correct	211 ms	57436 KB	Output is correct
9	Correct	406 ms	66488 KB	Output is correct
10	Correct	268 ms	60108 KB	Output is correct
11	Correct	279 ms	66228 KB	Output is correct
12	Correct	6 ms	34904 KB	Output is correct
13	Correct	5 ms	34904 KB	Output is correct
14	Correct	7 ms	34908 KB	Output is correct
15	Correct	5 ms	34908 KB	Output is correct
16	Correct	5 ms	35016 KB	Output is correct
17	Correct	6 ms	34904 KB	Output is correct
18	Correct	5 ms	34908 KB	Output is correct
19	Correct	6 ms	34908 KB	Output is correct
20	Correct	6 ms	34908 KB	Output is correct
21	Correct	5 ms	34908 KB	Output is correct
22	Correct	6 ms	34908 KB	Output is correct
23	Correct	6 ms	34908 KB	Output is correct
24	Correct	6 ms	34908 KB	Output is correct
25	Correct	6 ms	34908 KB	Output is correct
26	Correct	5 ms	34908 KB	Output is correct
27	Correct	5 ms	34908 KB	Output is correct
28	Correct	9 ms	35164 KB	Output is correct
29	Correct	8 ms	35120 KB	Output is correct
30	Correct	10 ms	35160 KB	Output is correct
31	Correct	8 ms	35016 KB	Output is correct
32	Correct	9 ms	35164 KB	Output is correct
33	Correct	8 ms	35164 KB	Output is correct
34	Correct	9 ms	35160 KB	Output is correct
35	Correct	348 ms	66240 KB	Output is correct
36	Correct	325 ms	64728 KB	Output is correct
37	Correct	355 ms	69560 KB	Output is correct
38	Correct	326 ms	64700 KB	Output is correct
39	Correct	352 ms	63412 KB	Output is correct
40	Correct	328 ms	66228 KB	Output is correct
41	Correct	418 ms	61008 KB	Output is correct
42	Correct	152 ms	46780 KB	Output is correct
43	Correct	180 ms	57604 KB	Output is correct
44	Correct	350 ms	56144 KB	Output is correct
45	Correct	388 ms	67780 KB	Output is correct
46	Correct	291 ms	61012 KB	Output is correct
47	Correct	288 ms	61012 KB	Output is correct
48	Correct	456 ms	69440 KB	Output is correct
49	Correct	395 ms	64704 KB	Output is correct
50	Correct	346 ms	60064 KB	Output is correct
51	Correct	406 ms	72532 KB	Output is correct
52	Correct	7 ms	34996 KB	Output is correct
53	Correct	520 ms	60944 KB	Output is correct
54	Correct	415 ms	56140 KB	Output is correct
55	Correct	465 ms	67836 KB	Output is correct
56	Correct	383 ms	60868 KB	Output is correct
57	Correct	406 ms	64712 KB	Output is correct
58	Correct	442 ms	78780 KB	Output is correct
59	Incorrect	391 ms	78896 KB	Output isn't correct
60	Halted	0 ms	0 KB	-

Subtask #8
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	391 ms	59988 KB	Output is correct
2	Correct	415 ms	70344 KB	Output is correct
3	Correct	398 ms	66488 KB	Output is correct
4	Correct	385 ms	56616 KB	Output is correct
5	Correct	6 ms	34904 KB	Output is correct
6	Correct	394 ms	62148 KB	Output is correct
7	Correct	181 ms	43700 KB	Output is correct
8	Correct	211 ms	57436 KB	Output is correct
9	Correct	406 ms	66488 KB	Output is correct
10	Correct	268 ms	60108 KB	Output is correct
11	Correct	279 ms	66228 KB	Output is correct
12	Correct	6 ms	34904 KB	Output is correct
13	Correct	5 ms	34904 KB	Output is correct
14	Correct	7 ms	34908 KB	Output is correct
15	Correct	5 ms	34908 KB	Output is correct
16	Correct	5 ms	35016 KB	Output is correct
17	Correct	6 ms	34904 KB	Output is correct
18	Correct	5 ms	34908 KB	Output is correct
19	Correct	6 ms	34908 KB	Output is correct
20	Correct	6 ms	34908 KB	Output is correct
21	Correct	5 ms	34908 KB	Output is correct
22	Correct	6 ms	34908 KB	Output is correct
23	Correct	6 ms	34908 KB	Output is correct
24	Correct	6 ms	34908 KB	Output is correct
25	Correct	6 ms	34908 KB	Output is correct
26	Correct	5 ms	34908 KB	Output is correct
27	Correct	5 ms	34908 KB	Output is correct
28	Correct	9 ms	35164 KB	Output is correct
29	Correct	8 ms	35120 KB	Output is correct
30	Correct	10 ms	35160 KB	Output is correct
31	Correct	8 ms	35016 KB	Output is correct
32	Correct	9 ms	35164 KB	Output is correct
33	Correct	8 ms	35164 KB	Output is correct
34	Correct	9 ms	35160 KB	Output is correct
35	Correct	348 ms	66240 KB	Output is correct
36	Correct	325 ms	64728 KB	Output is correct
37	Correct	355 ms	69560 KB	Output is correct
38	Correct	326 ms	64700 KB	Output is correct
39	Correct	352 ms	63412 KB	Output is correct
40	Correct	328 ms	66228 KB	Output is correct
41	Correct	418 ms	61008 KB	Output is correct
42	Correct	152 ms	46780 KB	Output is correct
43	Correct	180 ms	57604 KB	Output is correct
44	Correct	350 ms	56144 KB	Output is correct
45	Correct	388 ms	67780 KB	Output is correct
46	Correct	291 ms	61012 KB	Output is correct
47	Correct	288 ms	61012 KB	Output is correct
48	Correct	456 ms	69440 KB	Output is correct
49	Correct	395 ms	64704 KB	Output is correct
50	Correct	346 ms	60064 KB	Output is correct
51	Correct	406 ms	72532 KB	Output is correct
52	Correct	7 ms	34996 KB	Output is correct
53	Correct	520 ms	60944 KB	Output is correct
54	Correct	415 ms	56140 KB	Output is correct
55	Correct	465 ms	67836 KB	Output is correct
56	Correct	383 ms	60868 KB	Output is correct
57	Correct	2138 ms	180228 KB	Output is correct
58	Correct	2005 ms	156760 KB	Output is correct
59	Correct	1735 ms	154260 KB	Output is correct
60	Correct	2152 ms	224712 KB	Output is correct
61	Correct	2696 ms	172748 KB	Output is correct
62	Correct	2141 ms	146604 KB	Output is correct
63	Correct	2519 ms	206348 KB	Output is correct
64	Correct	2017 ms	156816 KB	Output is correct
65	Correct	406 ms	64712 KB	Output is correct
66	Correct	442 ms	78780 KB	Output is correct
67	Incorrect	391 ms	78896 KB	Output isn't correct
68	Halted	0 ms	0 KB	-

Submission #1070246

Compilation message