답안 #1070280

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1070280	2024-08-22T12:44:33 Z	Ahmed57	Two Dishes (JOI19_dishes)	C++17	100 / 100	2896 ms	242440 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++){
        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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	429 ms	67048 KB	Output is correct
2	Correct	460 ms	77804 KB	Output is correct
3	Correct	389 ms	73564 KB	Output is correct
4	Correct	430 ms	63984 KB	Output is correct
5	Correct	5 ms	34908 KB	Output is correct
6	Correct	424 ms	69220 KB	Output is correct
7	Correct	212 ms	47524 KB	Output is correct
8	Correct	227 ms	61368 KB	Output is correct
9	Correct	422 ms	73932 KB	Output is correct
10	Correct	277 ms	64076 KB	Output is correct
11	Correct	304 ms	71188 KB	Output is correct

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	34904 KB	Output is correct
2	Correct	5 ms	34908 KB	Output is correct
3	Correct	6 ms	35056 KB	Output is correct
4	Correct	6 ms	34908 KB	Output is correct
5	Correct	5 ms	35020 KB	Output is correct
6	Correct	7 ms	34908 KB	Output is correct
7	Correct	5 ms	34908 KB	Output is correct
8	Correct	5 ms	34908 KB	Output is correct
9	Correct	5 ms	34904 KB	Output is correct
10	Correct	6 ms	34908 KB	Output is correct
11	Correct	5 ms	35012 KB	Output is correct
12	Correct	6 ms	35056 KB	Output is correct
13	Correct	6 ms	34908 KB	Output is correct
14	Correct	7 ms	35020 KB	Output is correct
15	Correct	5 ms	35024 KB	Output is correct
16	Correct	6 ms	34904 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	34904 KB	Output is correct
2	Correct	5 ms	34908 KB	Output is correct
3	Correct	6 ms	35056 KB	Output is correct
4	Correct	6 ms	34908 KB	Output is correct
5	Correct	5 ms	35020 KB	Output is correct
6	Correct	7 ms	34908 KB	Output is correct
7	Correct	5 ms	34908 KB	Output is correct
8	Correct	5 ms	34908 KB	Output is correct
9	Correct	5 ms	34904 KB	Output is correct
10	Correct	6 ms	34908 KB	Output is correct
11	Correct	5 ms	35012 KB	Output is correct
12	Correct	6 ms	35056 KB	Output is correct
13	Correct	6 ms	34908 KB	Output is correct
14	Correct	7 ms	35020 KB	Output is correct
15	Correct	5 ms	35024 KB	Output is correct
16	Correct	6 ms	34904 KB	Output is correct
17	Correct	8 ms	35164 KB	Output is correct
18	Correct	9 ms	35164 KB	Output is correct
19	Correct	9 ms	35164 KB	Output is correct
20	Correct	8 ms	35164 KB	Output is correct
21	Correct	13 ms	35164 KB	Output is correct
22	Correct	9 ms	35108 KB	Output is correct
23	Correct	10 ms	35164 KB	Output is correct

Subtask #4
39.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	34904 KB	Output is correct
2	Correct	5 ms	34908 KB	Output is correct
3	Correct	6 ms	35056 KB	Output is correct
4	Correct	6 ms	34908 KB	Output is correct
5	Correct	5 ms	35020 KB	Output is correct
6	Correct	7 ms	34908 KB	Output is correct
7	Correct	5 ms	34908 KB	Output is correct
8	Correct	5 ms	34908 KB	Output is correct
9	Correct	5 ms	34904 KB	Output is correct
10	Correct	6 ms	34908 KB	Output is correct
11	Correct	5 ms	35012 KB	Output is correct
12	Correct	6 ms	35056 KB	Output is correct
13	Correct	6 ms	34908 KB	Output is correct
14	Correct	7 ms	35020 KB	Output is correct
15	Correct	5 ms	35024 KB	Output is correct
16	Correct	6 ms	34904 KB	Output is correct
17	Correct	8 ms	35164 KB	Output is correct
18	Correct	9 ms	35164 KB	Output is correct
19	Correct	9 ms	35164 KB	Output is correct
20	Correct	8 ms	35164 KB	Output is correct
21	Correct	13 ms	35164 KB	Output is correct
22	Correct	9 ms	35108 KB	Output is correct
23	Correct	10 ms	35164 KB	Output is correct
24	Correct	342 ms	72956 KB	Output is correct
25	Correct	332 ms	70588 KB	Output is correct
26	Correct	367 ms	75284 KB	Output is correct
27	Correct	403 ms	71064 KB	Output is correct
28	Correct	365 ms	69412 KB	Output is correct
29	Correct	456 ms	72648 KB	Output is correct
30	Correct	483 ms	66924 KB	Output is correct
31	Correct	203 ms	49832 KB	Output is correct
32	Correct	188 ms	60700 KB	Output is correct
33	Correct	365 ms	61840 KB	Output is correct
34	Correct	436 ms	73452 KB	Output is correct
35	Correct	307 ms	63660 KB	Output is correct
36	Correct	265 ms	63568 KB	Output is correct

Subtask #5
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	34904 KB	Output is correct
2	Correct	5 ms	34908 KB	Output is correct
3	Correct	6 ms	35056 KB	Output is correct
4	Correct	6 ms	34908 KB	Output is correct
5	Correct	5 ms	35020 KB	Output is correct
6	Correct	7 ms	34908 KB	Output is correct
7	Correct	5 ms	34908 KB	Output is correct
8	Correct	5 ms	34908 KB	Output is correct
9	Correct	5 ms	34904 KB	Output is correct
10	Correct	6 ms	34908 KB	Output is correct
11	Correct	5 ms	35012 KB	Output is correct
12	Correct	6 ms	35056 KB	Output is correct
13	Correct	6 ms	34908 KB	Output is correct
14	Correct	7 ms	35020 KB	Output is correct
15	Correct	5 ms	35024 KB	Output is correct
16	Correct	6 ms	34904 KB	Output is correct
17	Correct	8 ms	35164 KB	Output is correct
18	Correct	9 ms	35164 KB	Output is correct
19	Correct	9 ms	35164 KB	Output is correct
20	Correct	8 ms	35164 KB	Output is correct
21	Correct	13 ms	35164 KB	Output is correct
22	Correct	9 ms	35108 KB	Output is correct
23	Correct	10 ms	35164 KB	Output is correct
24	Correct	342 ms	72956 KB	Output is correct
25	Correct	332 ms	70588 KB	Output is correct
26	Correct	367 ms	75284 KB	Output is correct
27	Correct	403 ms	71064 KB	Output is correct
28	Correct	365 ms	69412 KB	Output is correct
29	Correct	456 ms	72648 KB	Output is correct
30	Correct	483 ms	66924 KB	Output is correct
31	Correct	203 ms	49832 KB	Output is correct
32	Correct	188 ms	60700 KB	Output is correct
33	Correct	365 ms	61840 KB	Output is correct
34	Correct	436 ms	73452 KB	Output is correct
35	Correct	307 ms	63660 KB	Output is correct
36	Correct	265 ms	63568 KB	Output is correct
37	Correct	402 ms	76920 KB	Output is correct
38	Correct	363 ms	72232 KB	Output is correct
39	Correct	342 ms	65988 KB	Output is correct
40	Correct	457 ms	78412 KB	Output is correct
41	Correct	5 ms	34908 KB	Output is correct
42	Correct	483 ms	68644 KB	Output is correct
43	Correct	399 ms	63300 KB	Output is correct
44	Correct	439 ms	74948 KB	Output is correct
45	Correct	321 ms	65108 KB	Output is correct

Subtask #6
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	34904 KB	Output is correct
2	Correct	5 ms	34908 KB	Output is correct
3	Correct	6 ms	35056 KB	Output is correct
4	Correct	6 ms	34908 KB	Output is correct
5	Correct	5 ms	35020 KB	Output is correct
6	Correct	7 ms	34908 KB	Output is correct
7	Correct	5 ms	34908 KB	Output is correct
8	Correct	5 ms	34908 KB	Output is correct
9	Correct	5 ms	34904 KB	Output is correct
10	Correct	6 ms	34908 KB	Output is correct
11	Correct	5 ms	35012 KB	Output is correct
12	Correct	6 ms	35056 KB	Output is correct
13	Correct	6 ms	34908 KB	Output is correct
14	Correct	7 ms	35020 KB	Output is correct
15	Correct	5 ms	35024 KB	Output is correct
16	Correct	6 ms	34904 KB	Output is correct
17	Correct	8 ms	35164 KB	Output is correct
18	Correct	9 ms	35164 KB	Output is correct
19	Correct	9 ms	35164 KB	Output is correct
20	Correct	8 ms	35164 KB	Output is correct
21	Correct	13 ms	35164 KB	Output is correct
22	Correct	9 ms	35108 KB	Output is correct
23	Correct	10 ms	35164 KB	Output is correct
24	Correct	342 ms	72956 KB	Output is correct
25	Correct	332 ms	70588 KB	Output is correct
26	Correct	367 ms	75284 KB	Output is correct
27	Correct	403 ms	71064 KB	Output is correct
28	Correct	365 ms	69412 KB	Output is correct
29	Correct	456 ms	72648 KB	Output is correct
30	Correct	483 ms	66924 KB	Output is correct
31	Correct	203 ms	49832 KB	Output is correct
32	Correct	188 ms	60700 KB	Output is correct
33	Correct	365 ms	61840 KB	Output is correct
34	Correct	436 ms	73452 KB	Output is correct
35	Correct	307 ms	63660 KB	Output is correct
36	Correct	265 ms	63568 KB	Output is correct
37	Correct	402 ms	76920 KB	Output is correct
38	Correct	363 ms	72232 KB	Output is correct
39	Correct	342 ms	65988 KB	Output is correct
40	Correct	457 ms	78412 KB	Output is correct
41	Correct	5 ms	34908 KB	Output is correct
42	Correct	483 ms	68644 KB	Output is correct
43	Correct	399 ms	63300 KB	Output is correct
44	Correct	439 ms	74948 KB	Output is correct
45	Correct	321 ms	65108 KB	Output is correct
46	Correct	2001 ms	215932 KB	Output is correct
47	Correct	1987 ms	192684 KB	Output is correct
48	Correct	1652 ms	162692 KB	Output is correct
49	Correct	2020 ms	224608 KB	Output is correct
50	Correct	2732 ms	173052 KB	Output is correct
51	Correct	2180 ms	146316 KB	Output is correct
52	Correct	2374 ms	204736 KB	Output is correct
53	Correct	1953 ms	157384 KB	Output is correct

Subtask #7
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	429 ms	67048 KB	Output is correct
2	Correct	460 ms	77804 KB	Output is correct
3	Correct	389 ms	73564 KB	Output is correct
4	Correct	430 ms	63984 KB	Output is correct
5	Correct	5 ms	34908 KB	Output is correct
6	Correct	424 ms	69220 KB	Output is correct
7	Correct	212 ms	47524 KB	Output is correct
8	Correct	227 ms	61368 KB	Output is correct
9	Correct	422 ms	73932 KB	Output is correct
10	Correct	277 ms	64076 KB	Output is correct
11	Correct	304 ms	71188 KB	Output is correct
12	Correct	5 ms	34904 KB	Output is correct
13	Correct	5 ms	34908 KB	Output is correct
14	Correct	6 ms	35056 KB	Output is correct
15	Correct	6 ms	34908 KB	Output is correct
16	Correct	5 ms	35020 KB	Output is correct
17	Correct	7 ms	34908 KB	Output is correct
18	Correct	5 ms	34908 KB	Output is correct
19	Correct	5 ms	34908 KB	Output is correct
20	Correct	5 ms	34904 KB	Output is correct
21	Correct	6 ms	34908 KB	Output is correct
22	Correct	5 ms	35012 KB	Output is correct
23	Correct	6 ms	35056 KB	Output is correct
24	Correct	6 ms	34908 KB	Output is correct
25	Correct	7 ms	35020 KB	Output is correct
26	Correct	5 ms	35024 KB	Output is correct
27	Correct	6 ms	34904 KB	Output is correct
28	Correct	8 ms	35164 KB	Output is correct
29	Correct	9 ms	35164 KB	Output is correct
30	Correct	9 ms	35164 KB	Output is correct
31	Correct	8 ms	35164 KB	Output is correct
32	Correct	13 ms	35164 KB	Output is correct
33	Correct	9 ms	35108 KB	Output is correct
34	Correct	10 ms	35164 KB	Output is correct
35	Correct	342 ms	72956 KB	Output is correct
36	Correct	332 ms	70588 KB	Output is correct
37	Correct	367 ms	75284 KB	Output is correct
38	Correct	403 ms	71064 KB	Output is correct
39	Correct	365 ms	69412 KB	Output is correct
40	Correct	456 ms	72648 KB	Output is correct
41	Correct	483 ms	66924 KB	Output is correct
42	Correct	203 ms	49832 KB	Output is correct
43	Correct	188 ms	60700 KB	Output is correct
44	Correct	365 ms	61840 KB	Output is correct
45	Correct	436 ms	73452 KB	Output is correct
46	Correct	307 ms	63660 KB	Output is correct
47	Correct	265 ms	63568 KB	Output is correct
48	Correct	402 ms	76920 KB	Output is correct
49	Correct	363 ms	72232 KB	Output is correct
50	Correct	342 ms	65988 KB	Output is correct
51	Correct	457 ms	78412 KB	Output is correct
52	Correct	5 ms	34908 KB	Output is correct
53	Correct	483 ms	68644 KB	Output is correct
54	Correct	399 ms	63300 KB	Output is correct
55	Correct	439 ms	74948 KB	Output is correct
56	Correct	321 ms	65108 KB	Output is correct
57	Correct	367 ms	64540 KB	Output is correct
58	Correct	421 ms	78684 KB	Output is correct
59	Correct	467 ms	78928 KB	Output is correct
60	Correct	352 ms	69628 KB	Output is correct
61	Correct	510 ms	81764 KB	Output is correct
62	Correct	5 ms	34908 KB	Output is correct
63	Correct	530 ms	71912 KB	Output is correct
64	Correct	508 ms	67216 KB	Output is correct
65	Correct	463 ms	73672 KB	Output is correct
66	Correct	360 ms	67084 KB	Output is correct

Subtask #8
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	429 ms	67048 KB	Output is correct
2	Correct	460 ms	77804 KB	Output is correct
3	Correct	389 ms	73564 KB	Output is correct
4	Correct	430 ms	63984 KB	Output is correct
5	Correct	5 ms	34908 KB	Output is correct
6	Correct	424 ms	69220 KB	Output is correct
7	Correct	212 ms	47524 KB	Output is correct
8	Correct	227 ms	61368 KB	Output is correct
9	Correct	422 ms	73932 KB	Output is correct
10	Correct	277 ms	64076 KB	Output is correct
11	Correct	304 ms	71188 KB	Output is correct
12	Correct	5 ms	34904 KB	Output is correct
13	Correct	5 ms	34908 KB	Output is correct
14	Correct	6 ms	35056 KB	Output is correct
15	Correct	6 ms	34908 KB	Output is correct
16	Correct	5 ms	35020 KB	Output is correct
17	Correct	7 ms	34908 KB	Output is correct
18	Correct	5 ms	34908 KB	Output is correct
19	Correct	5 ms	34908 KB	Output is correct
20	Correct	5 ms	34904 KB	Output is correct
21	Correct	6 ms	34908 KB	Output is correct
22	Correct	5 ms	35012 KB	Output is correct
23	Correct	6 ms	35056 KB	Output is correct
24	Correct	6 ms	34908 KB	Output is correct
25	Correct	7 ms	35020 KB	Output is correct
26	Correct	5 ms	35024 KB	Output is correct
27	Correct	6 ms	34904 KB	Output is correct
28	Correct	8 ms	35164 KB	Output is correct
29	Correct	9 ms	35164 KB	Output is correct
30	Correct	9 ms	35164 KB	Output is correct
31	Correct	8 ms	35164 KB	Output is correct
32	Correct	13 ms	35164 KB	Output is correct
33	Correct	9 ms	35108 KB	Output is correct
34	Correct	10 ms	35164 KB	Output is correct
35	Correct	342 ms	72956 KB	Output is correct
36	Correct	332 ms	70588 KB	Output is correct
37	Correct	367 ms	75284 KB	Output is correct
38	Correct	403 ms	71064 KB	Output is correct
39	Correct	365 ms	69412 KB	Output is correct
40	Correct	456 ms	72648 KB	Output is correct
41	Correct	483 ms	66924 KB	Output is correct
42	Correct	203 ms	49832 KB	Output is correct
43	Correct	188 ms	60700 KB	Output is correct
44	Correct	365 ms	61840 KB	Output is correct
45	Correct	436 ms	73452 KB	Output is correct
46	Correct	307 ms	63660 KB	Output is correct
47	Correct	265 ms	63568 KB	Output is correct
48	Correct	402 ms	76920 KB	Output is correct
49	Correct	363 ms	72232 KB	Output is correct
50	Correct	342 ms	65988 KB	Output is correct
51	Correct	457 ms	78412 KB	Output is correct
52	Correct	5 ms	34908 KB	Output is correct
53	Correct	483 ms	68644 KB	Output is correct
54	Correct	399 ms	63300 KB	Output is correct
55	Correct	439 ms	74948 KB	Output is correct
56	Correct	321 ms	65108 KB	Output is correct
57	Correct	2001 ms	215932 KB	Output is correct
58	Correct	1987 ms	192684 KB	Output is correct
59	Correct	1652 ms	162692 KB	Output is correct
60	Correct	2020 ms	224608 KB	Output is correct
61	Correct	2732 ms	173052 KB	Output is correct
62	Correct	2180 ms	146316 KB	Output is correct
63	Correct	2374 ms	204736 KB	Output is correct
64	Correct	1953 ms	157384 KB	Output is correct
65	Correct	367 ms	64540 KB	Output is correct
66	Correct	421 ms	78684 KB	Output is correct
67	Correct	467 ms	78928 KB	Output is correct
68	Correct	352 ms	69628 KB	Output is correct
69	Correct	510 ms	81764 KB	Output is correct
70	Correct	5 ms	34908 KB	Output is correct
71	Correct	530 ms	71912 KB	Output is correct
72	Correct	508 ms	67216 KB	Output is correct
73	Correct	463 ms	73672 KB	Output is correct
74	Correct	360 ms	67084 KB	Output is correct
75	Correct	1928 ms	171992 KB	Output is correct
76	Correct	2311 ms	242440 KB	Output is correct
77	Correct	2052 ms	240700 KB	Output is correct
78	Correct	1740 ms	178260 KB	Output is correct
79	Correct	2896 ms	190896 KB	Output is correct
80	Correct	2294 ms	165708 KB	Output is correct
81	Correct	2633 ms	195328 KB	Output is correct
82	Correct	2045 ms	166588 KB	Output is correct
83	Correct	2373 ms	181716 KB	Output is correct

답안 #1070280

Compilation message