답안 #640775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640775	2022-09-15T08:08:05 Z	wiktorlew	메기 농장 (IOI22_fish)	C++17	100 / 100	735 ms	113080 KB

fish

#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int N = 1e5 + 5;
const int M = 3e5 + 5;
const long long LL = 1e18;
ll ans;
map<ll, ll> dp[N][2];
vector<pair<ll, ll>> pref[N];
vector<int> wys[N];
ll max_weights(int n, int m, vector<int>X, vector<int>Y, vector<int>Z){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		pref[X[i]].pb({Y[i], Z[i]});
		wys[X[i]].pb(Y[i]);
	}
	for(int i = 0; i < n; ++i) {
        wys[i].pb(n);
        wys[i].pb(0);
        sort(wys[i].begin(), wys[i].end());
        wys[i].erase(unique(wys[i].begin(), wys[i].end()), wys[i].end());
    }
	for(int i=0;i<n;i++){
		sort(pref[i].begin(), pref[i].end());
		ll suma=0;
		for(int j=0;j<(int)pref[i].size();j++) {
            suma+=pref[i][j].second;
            pref[i][j].second = suma;
        }
        pref[i].insert(pref[i].begin(), make_pair(-1, 0));
	}
	for(int i=1;i<n;i++){
		vector<pair<ll, ll>> spr1, spr2;
		for(ll pom : wys[i-1]){
			dp[i][0][0]=max({dp[i][0][0], dp[i-1][0][pom], dp[i-1][1][pom]});
			dp[i][1][0]=max({dp[i][1][0], dp[i-1][0][pom], dp[i-1][1][pom]});
			ll res=0;
			if(!spr1.empty()) res=spr1.back().second;
			auto it = upper_bound(pref[i-1].begin(), pref[i-1].end(), make_pair(pom-1, LLONG_MAX));
			it--;
			res=max(res, dp[i-1][0][pom]-it->second);
			spr1.pb({pom, res});
		}
		reverse(wys[i-1].begin(), wys[i-1].end());
		for(ll pom : wys[i-1]){
			ll res=0;
			if(!spr2.empty()) res=spr2.back().second;
			auto it = upper_bound(pref[i].begin(), pref[i].end(), make_pair(pom-1, LLONG_MAX));
			it--;
			res = max(res, dp[i - 1][0][pom] + it->second);
            res = max(res, dp[i - 1][1][pom] + it->second);
            spr2.pb({pom, res});
		}
		reverse(spr2.begin(), spr2.end());
		for(ll pom : wys[i]){
			auto op1 = upper_bound(spr1.begin(), spr1.end(), make_pair(pom, LLONG_MAX));
			op1--;
			auto op2 = lower_bound(spr2.begin(), spr2.end(), make_pair(pom, LLONG_MIN));
			auto tmp1 = upper_bound(pref[i-1].begin(), pref[i-1].end(), make_pair(pom-1, LLONG_MAX));
			tmp1--;
			dp[i][0][pom]=max(dp[i][0][pom], op1->second + tmp1->second);
			auto tmp2 = upper_bound(pref[i].begin(), pref[i].end(), make_pair(pom-1, LLONG_MAX));
			tmp2--;
			dp[i][1][pom]=max(dp[i][1][pom], op2->second - tmp2->second);
		}
	}
	for(int i=0;i<=n;i++){
		ans = max({ans, dp[n-1][0][i], dp[n-1][1][i]});
	}
	return ans;
}

Subtask #1
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	246 ms	68512 KB	Output is correct
2	Correct	297 ms	76420 KB	Output is correct
3	Correct	141 ms	58188 KB	Output is correct
4	Correct	131 ms	58208 KB	Output is correct
5	Correct	735 ms	110808 KB	Output is correct
6	Correct	422 ms	112900 KB	Output is correct

Subtask #2
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	14292 KB	Output is correct
2	Correct	405 ms	83724 KB	Output is correct
3	Correct	458 ms	95028 KB	Output is correct
4	Correct	221 ms	68568 KB	Output is correct
5	Correct	263 ms	76468 KB	Output is correct
6	Correct	7 ms	14292 KB	Output is correct
7	Correct	8 ms	14388 KB	Output is correct
8	Correct	7 ms	14292 KB	Output is correct
9	Correct	7 ms	14292 KB	Output is correct
10	Correct	117 ms	58164 KB	Output is correct
11	Correct	117 ms	58208 KB	Output is correct
12	Correct	266 ms	68548 KB	Output is correct
13	Correct	303 ms	76496 KB	Output is correct
14	Correct	233 ms	68552 KB	Output is correct
15	Correct	280 ms	74824 KB	Output is correct
16	Correct	244 ms	68680 KB	Output is correct
17	Correct	261 ms	74612 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	123 ms	58188 KB	Output is correct
2	Correct	119 ms	58176 KB	Output is correct
3	Correct	147 ms	57092 KB	Output is correct
4	Correct	146 ms	59724 KB	Output is correct
5	Correct	182 ms	65196 KB	Output is correct
6	Correct	182 ms	65996 KB	Output is correct
7	Correct	189 ms	66528 KB	Output is correct
8	Correct	186 ms	66568 KB	Output is correct

Subtask #4
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	14312 KB	Output is correct
2	Correct	7 ms	14292 KB	Output is correct
3	Correct	7 ms	14304 KB	Output is correct
4	Correct	7 ms	14344 KB	Output is correct
5	Correct	7 ms	14292 KB	Output is correct
6	Correct	7 ms	14296 KB	Output is correct
7	Correct	7 ms	14292 KB	Output is correct
8	Correct	9 ms	14292 KB	Output is correct
9	Correct	8 ms	14420 KB	Output is correct
10	Correct	9 ms	14876 KB	Output is correct
11	Correct	8 ms	14548 KB	Output is correct
12	Correct	8 ms	14676 KB	Output is correct
13	Correct	8 ms	14420 KB	Output is correct
14	Correct	8 ms	14548 KB	Output is correct

Subtask #5
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	14312 KB	Output is correct
2	Correct	7 ms	14292 KB	Output is correct
3	Correct	7 ms	14304 KB	Output is correct
4	Correct	7 ms	14344 KB	Output is correct
5	Correct	7 ms	14292 KB	Output is correct
6	Correct	7 ms	14296 KB	Output is correct
7	Correct	7 ms	14292 KB	Output is correct
8	Correct	9 ms	14292 KB	Output is correct
9	Correct	8 ms	14420 KB	Output is correct
10	Correct	9 ms	14876 KB	Output is correct
11	Correct	8 ms	14548 KB	Output is correct
12	Correct	8 ms	14676 KB	Output is correct
13	Correct	8 ms	14420 KB	Output is correct
14	Correct	8 ms	14548 KB	Output is correct
15	Correct	8 ms	14548 KB	Output is correct
16	Correct	9 ms	14788 KB	Output is correct
17	Correct	59 ms	22800 KB	Output is correct
18	Correct	59 ms	23352 KB	Output is correct
19	Correct	55 ms	23372 KB	Output is correct
20	Correct	54 ms	23224 KB	Output is correct
21	Correct	53 ms	23272 KB	Output is correct
22	Correct	117 ms	32152 KB	Output is correct
23	Correct	16 ms	16084 KB	Output is correct
24	Correct	40 ms	19972 KB	Output is correct
25	Correct	8 ms	14700 KB	Output is correct
26	Correct	16 ms	15956 KB	Output is correct

Subtask #6
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	14312 KB	Output is correct
2	Correct	7 ms	14292 KB	Output is correct
3	Correct	7 ms	14304 KB	Output is correct
4	Correct	7 ms	14344 KB	Output is correct
5	Correct	7 ms	14292 KB	Output is correct
6	Correct	7 ms	14296 KB	Output is correct
7	Correct	7 ms	14292 KB	Output is correct
8	Correct	9 ms	14292 KB	Output is correct
9	Correct	8 ms	14420 KB	Output is correct
10	Correct	9 ms	14876 KB	Output is correct
11	Correct	8 ms	14548 KB	Output is correct
12	Correct	8 ms	14676 KB	Output is correct
13	Correct	8 ms	14420 KB	Output is correct
14	Correct	8 ms	14548 KB	Output is correct
15	Correct	8 ms	14548 KB	Output is correct
16	Correct	9 ms	14788 KB	Output is correct
17	Correct	59 ms	22800 KB	Output is correct
18	Correct	59 ms	23352 KB	Output is correct
19	Correct	55 ms	23372 KB	Output is correct
20	Correct	54 ms	23224 KB	Output is correct
21	Correct	53 ms	23272 KB	Output is correct
22	Correct	117 ms	32152 KB	Output is correct
23	Correct	16 ms	16084 KB	Output is correct
24	Correct	40 ms	19972 KB	Output is correct
25	Correct	8 ms	14700 KB	Output is correct
26	Correct	16 ms	15956 KB	Output is correct
27	Correct	12 ms	16212 KB	Output is correct
28	Correct	272 ms	56776 KB	Output is correct
29	Correct	424 ms	73496 KB	Output is correct
30	Correct	324 ms	73332 KB	Output is correct
31	Correct	325 ms	73292 KB	Output is correct
32	Correct	368 ms	73616 KB	Output is correct
33	Correct	319 ms	73248 KB	Output is correct
34	Correct	329 ms	72700 KB	Output is correct
35	Correct	117 ms	37596 KB	Output is correct
36	Correct	358 ms	73036 KB	Output is correct

Subtask #7
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	123 ms	58188 KB	Output is correct
2	Correct	119 ms	58176 KB	Output is correct
3	Correct	147 ms	57092 KB	Output is correct
4	Correct	146 ms	59724 KB	Output is correct
5	Correct	182 ms	65196 KB	Output is correct
6	Correct	182 ms	65996 KB	Output is correct
7	Correct	189 ms	66528 KB	Output is correct
8	Correct	186 ms	66568 KB	Output is correct
9	Correct	230 ms	78392 KB	Output is correct
10	Correct	134 ms	49228 KB	Output is correct
11	Correct	275 ms	84472 KB	Output is correct
12	Correct	7 ms	14292 KB	Output is correct
13	Correct	7 ms	14392 KB	Output is correct
14	Correct	7 ms	14316 KB	Output is correct
15	Correct	7 ms	14292 KB	Output is correct
16	Correct	7 ms	14292 KB	Output is correct
17	Correct	7 ms	14292 KB	Output is correct
18	Correct	131 ms	58084 KB	Output is correct
19	Correct	123 ms	58104 KB	Output is correct
20	Correct	129 ms	58316 KB	Output is correct
21	Correct	146 ms	58196 KB	Output is correct
22	Correct	224 ms	76620 KB	Output is correct
23	Correct	304 ms	94704 KB	Output is correct
24	Correct	313 ms	97196 KB	Output is correct

Subtask #8
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	246 ms	68512 KB	Output is correct
2	Correct	297 ms	76420 KB	Output is correct
3	Correct	141 ms	58188 KB	Output is correct
4	Correct	131 ms	58208 KB	Output is correct
5	Correct	735 ms	110808 KB	Output is correct
6	Correct	422 ms	112900 KB	Output is correct
7	Correct	8 ms	14292 KB	Output is correct
8	Correct	405 ms	83724 KB	Output is correct
9	Correct	458 ms	95028 KB	Output is correct
10	Correct	221 ms	68568 KB	Output is correct
11	Correct	263 ms	76468 KB	Output is correct
12	Correct	7 ms	14292 KB	Output is correct
13	Correct	8 ms	14388 KB	Output is correct
14	Correct	7 ms	14292 KB	Output is correct
15	Correct	7 ms	14292 KB	Output is correct
16	Correct	117 ms	58164 KB	Output is correct
17	Correct	117 ms	58208 KB	Output is correct
18	Correct	266 ms	68548 KB	Output is correct
19	Correct	303 ms	76496 KB	Output is correct
20	Correct	233 ms	68552 KB	Output is correct
21	Correct	280 ms	74824 KB	Output is correct
22	Correct	244 ms	68680 KB	Output is correct
23	Correct	261 ms	74612 KB	Output is correct
24	Correct	123 ms	58188 KB	Output is correct
25	Correct	119 ms	58176 KB	Output is correct
26	Correct	147 ms	57092 KB	Output is correct
27	Correct	146 ms	59724 KB	Output is correct
28	Correct	182 ms	65196 KB	Output is correct
29	Correct	182 ms	65996 KB	Output is correct
30	Correct	189 ms	66528 KB	Output is correct
31	Correct	186 ms	66568 KB	Output is correct
32	Correct	7 ms	14312 KB	Output is correct
33	Correct	7 ms	14292 KB	Output is correct
34	Correct	7 ms	14304 KB	Output is correct
35	Correct	7 ms	14344 KB	Output is correct
36	Correct	7 ms	14292 KB	Output is correct
37	Correct	7 ms	14296 KB	Output is correct
38	Correct	7 ms	14292 KB	Output is correct
39	Correct	9 ms	14292 KB	Output is correct
40	Correct	8 ms	14420 KB	Output is correct
41	Correct	9 ms	14876 KB	Output is correct
42	Correct	8 ms	14548 KB	Output is correct
43	Correct	8 ms	14676 KB	Output is correct
44	Correct	8 ms	14420 KB	Output is correct
45	Correct	8 ms	14548 KB	Output is correct
46	Correct	8 ms	14548 KB	Output is correct
47	Correct	9 ms	14788 KB	Output is correct
48	Correct	59 ms	22800 KB	Output is correct
49	Correct	59 ms	23352 KB	Output is correct
50	Correct	55 ms	23372 KB	Output is correct
51	Correct	54 ms	23224 KB	Output is correct
52	Correct	53 ms	23272 KB	Output is correct
53	Correct	117 ms	32152 KB	Output is correct
54	Correct	16 ms	16084 KB	Output is correct
55	Correct	40 ms	19972 KB	Output is correct
56	Correct	8 ms	14700 KB	Output is correct
57	Correct	16 ms	15956 KB	Output is correct
58	Correct	12 ms	16212 KB	Output is correct
59	Correct	272 ms	56776 KB	Output is correct
60	Correct	424 ms	73496 KB	Output is correct
61	Correct	324 ms	73332 KB	Output is correct
62	Correct	325 ms	73292 KB	Output is correct
63	Correct	368 ms	73616 KB	Output is correct
64	Correct	319 ms	73248 KB	Output is correct
65	Correct	329 ms	72700 KB	Output is correct
66	Correct	117 ms	37596 KB	Output is correct
67	Correct	358 ms	73036 KB	Output is correct
68	Correct	230 ms	78392 KB	Output is correct
69	Correct	134 ms	49228 KB	Output is correct
70	Correct	275 ms	84472 KB	Output is correct
71	Correct	7 ms	14292 KB	Output is correct
72	Correct	7 ms	14392 KB	Output is correct
73	Correct	7 ms	14316 KB	Output is correct
74	Correct	7 ms	14292 KB	Output is correct
75	Correct	7 ms	14292 KB	Output is correct
76	Correct	7 ms	14292 KB	Output is correct
77	Correct	131 ms	58084 KB	Output is correct
78	Correct	123 ms	58104 KB	Output is correct
79	Correct	129 ms	58316 KB	Output is correct
80	Correct	146 ms	58196 KB	Output is correct
81	Correct	224 ms	76620 KB	Output is correct
82	Correct	304 ms	94704 KB	Output is correct
83	Correct	313 ms	97196 KB	Output is correct
84	Correct	656 ms	109472 KB	Output is correct
85	Correct	652 ms	112316 KB	Output is correct
86	Correct	433 ms	110336 KB	Output is correct
87	Correct	451 ms	113080 KB	Output is correct
88	Correct	8 ms	14292 KB	Output is correct
89	Correct	450 ms	112392 KB	Output is correct
90	Correct	405 ms	109144 KB	Output is correct
91	Correct	388 ms	108988 KB	Output is correct

답안 #640775

Compilation message