oj.uz

답안 #629449

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
629449 2022-08-14T13:46:04 Z handlename 메기 농장 (IOI22_fish) C++17
100 / 100
 505 ms 65572 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
 
vector<pair<int,long long> > arr[100005];
long long qry(int col,int height){ //prefixsum of col to height
	if (arr[col].empty()) return 0;
	pair<int,long long> lol=mp(height,1e18);
	int pos=upper_bound(arr[col].begin(),arr[col].end(),lol)-arr[col].begin();
	pos--;
	return arr[col][pos].second;
}
vector<long long> dp1[100005]; //col,height,increasing
vector<long long> dp2[100005]; //col,height,decreasing
vector<long long> whack[100005];
long long max_weights(int n,int m,vector<int> x,vector<int> y,vector<int> w){
	for (int i=0;i<m;i++){
		x[i]++;
		y[i]++;
		arr[x[i]].pb(mp(y[i],w[i]));
	}
	for (int i=1;i<=n;i++){
		arr[i].pb(mp(0,0));
		sort(arr[i].begin(),arr[i].end());
		for (int j=1;j<(int)arr[i].size();j++){
			arr[i][j].second+=arr[i][j-1].second;
		}
		for (auto j:arr[i]){
			whack[i].pb(j.first);
			whack[i+1].pb(j.first);
			whack[i-1].pb(j.first);
		}
	}
	for (int i=0;i<=n;i++){
		sort(whack[i].begin(),whack[i].end());
		whack[i].erase(unique(whack[i].begin(),whack[i].end()),whack[i].end());
		for (int j=0;j<(int) whack[i].size();j++){
			dp1[i].pb(0);
			dp2[i].pb(0);
		}
	}
	for (int i=1;i<=n;i++){ //col
		long long maxi=0,id=0;
		for (int j=0;j<(int)whack[i].size();j++){
			int k=whack[i][j];
			while (id<(int)whack[i-1].size() && whack[i-1][id]<=k){
				maxi=max(maxi,dp1[i-1][id]-qry(i,whack[i-1][id])-qry(i-1,whack[i-1][id]));
				id++;
			}
			dp1[i][j]=maxi+qry(i-1,k)+qry(i+1,k);
		}
		if (i>=2){
			maxi=0;
			id=0;
			for (int j=0;j<(int)whack[i].size();j++){
				int k=whack[i][j];
				while (id<(int)whack[i-2].size() && whack[i-2][id]<=k){
					maxi=max(maxi,dp2[i-2][id]-qry(i-1,whack[i-2][id]));
					id++;
				}
				dp1[i][j]=max(dp1[i][j],maxi+qry(i-1,k)+qry(i+1,k));
			}
			maxi=0;
			id=whack[i-2].size()-1;
			for (int j=whack[i].size()-1;j>=0;j--){
				int k=whack[i][j];
				while (id>=0 && whack[i-2][id]>=k){
					maxi=max(maxi,dp2[i-2][id]);
					id--;
				}
				dp1[i][j]=max(dp1[i][j],maxi+qry(i+1,k));
			}
		}
		maxi=0;
		id=whack[i-1].size()-1;
		for (int j=whack[i].size()-1;j>=0;j--){
			int k=whack[i][j];
			while (id>=0 && whack[i-1][id]>=k){
				maxi=max(maxi,dp2[i-1][id]);
				id--;
			}
			dp2[i][j]=maxi+qry(i+1,k)-qry(i,k);
		}
		for (int j=0;j<(int)whack[i].size();j++){
			dp2[i][j]=max(dp2[i][j],dp1[i][j]);
		}
	}
	long long ans=0;
	for (int j=0;j<(int)dp2[n].size();j++){
		ans=max(ans,dp2[n][j]);
	}
	return ans;
}

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 31668 KB Output is correct
2 Correct 134 ms 35028 KB Output is correct
3 Correct 40 ms 23756 KB Output is correct
4 Correct 41 ms 23712 KB Output is correct
5 Correct 403 ms 59116 KB Output is correct
6 Correct 412 ms 65572 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 222 ms 38364 KB Output is correct
3 Correct 258 ms 42928 KB Output is correct
4 Correct 111 ms 31548 KB Output is correct
5 Correct 132 ms 34924 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9700 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 6 ms 9604 KB Output is correct
10 Correct 39 ms 23720 KB Output is correct
11 Correct 43 ms 23660 KB Output is correct
12 Correct 120 ms 31664 KB Output is correct
13 Correct 146 ms 35036 KB Output is correct
14 Correct 125 ms 32480 KB Output is correct
15 Correct 131 ms 32772 KB Output is correct
16 Correct 123 ms 32480 KB Output is correct
17 Correct 134 ms 34696 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 23764 KB Output is correct
2 Correct 40 ms 23708 KB Output is correct
3 Correct 71 ms 26308 KB Output is correct
4 Correct 67 ms 26284 KB Output is correct
5 Correct 101 ms 31352 KB Output is correct
6 Correct 99 ms 31364 KB Output is correct
7 Correct 107 ms 31416 KB Output is correct
8 Correct 104 ms 31356 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9688 KB Output is correct
3 Correct 5 ms 9700 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9940 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 7 ms 9808 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9688 KB Output is correct
3 Correct 5 ms 9700 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9940 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 7 ms 9808 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 6 ms 9684 KB Output is correct
16 Correct 8 ms 9952 KB Output is correct
17 Correct 54 ms 14588 KB Output is correct
18 Correct 44 ms 14804 KB Output is correct
19 Correct 39 ms 14676 KB Output is correct
20 Correct 38 ms 14388 KB Output is correct
21 Correct 35 ms 14448 KB Output is correct
22 Correct 73 ms 19116 KB Output is correct
23 Correct 17 ms 10964 KB Output is correct
24 Correct 49 ms 13496 KB Output is correct
25 Correct 6 ms 9812 KB Output is correct
26 Correct 16 ms 10964 KB Output is correct

Subtask #6
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9688 KB Output is correct
3 Correct 5 ms 9700 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 5 ms 9684 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 5 ms 9684 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 6 ms 9940 KB Output is correct
11 Correct 6 ms 9684 KB Output is correct
12 Correct 7 ms 9808 KB Output is correct
13 Correct 5 ms 9684 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 6 ms 9684 KB Output is correct
16 Correct 8 ms 9952 KB Output is correct
17 Correct 54 ms 14588 KB Output is correct
18 Correct 44 ms 14804 KB Output is correct
19 Correct 39 ms 14676 KB Output is correct
20 Correct 38 ms 14388 KB Output is correct
21 Correct 35 ms 14448 KB Output is correct
22 Correct 73 ms 19116 KB Output is correct
23 Correct 17 ms 10964 KB Output is correct
24 Correct 49 ms 13496 KB Output is correct
25 Correct 6 ms 9812 KB Output is correct
26 Correct 16 ms 10964 KB Output is correct
27 Correct 8 ms 10324 KB Output is correct
28 Correct 219 ms 31880 KB Output is correct
29 Correct 320 ms 40728 KB Output is correct
30 Correct 445 ms 59468 KB Output is correct
31 Correct 456 ms 59064 KB Output is correct
32 Correct 240 ms 42316 KB Output is correct
33 Correct 466 ms 59328 KB Output is correct
34 Correct 451 ms 59284 KB Output is correct
35 Correct 147 ms 25496 KB Output is correct
36 Correct 433 ms 52900 KB Output is correct

Subtask #7
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 23764 KB Output is correct
2 Correct 40 ms 23708 KB Output is correct
3 Correct 71 ms 26308 KB Output is correct
4 Correct 67 ms 26284 KB Output is correct
5 Correct 101 ms 31352 KB Output is correct
6 Correct 99 ms 31364 KB Output is correct
7 Correct 107 ms 31416 KB Output is correct
8 Correct 104 ms 31356 KB Output is correct
9 Correct 124 ms 34928 KB Output is correct
10 Correct 91 ms 27884 KB Output is correct
11 Correct 168 ms 46128 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 7 ms 9684 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 5 ms 9684 KB Output is correct
16 Correct 5 ms 9684 KB Output is correct
17 Correct 5 ms 9684 KB Output is correct
18 Correct 40 ms 23688 KB Output is correct
19 Correct 39 ms 23736 KB Output is correct
20 Correct 43 ms 23728 KB Output is correct
21 Correct 40 ms 23784 KB Output is correct
22 Correct 162 ms 36088 KB Output is correct
23 Correct 217 ms 50252 KB Output is correct
24 Correct 198 ms 50964 KB Output is correct

Subtask #8
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 31668 KB Output is correct
2 Correct 134 ms 35028 KB Output is correct
3 Correct 40 ms 23756 KB Output is correct
4 Correct 41 ms 23712 KB Output is correct
5 Correct 403 ms 59116 KB Output is correct
6 Correct 412 ms 65572 KB Output is correct
7 Correct 5 ms 9684 KB Output is correct
8 Correct 222 ms 38364 KB Output is correct
9 Correct 258 ms 42928 KB Output is correct
10 Correct 111 ms 31548 KB Output is correct
11 Correct 132 ms 34924 KB Output is correct
12 Correct 5 ms 9684 KB Output is correct
13 Correct 5 ms 9700 KB Output is correct
14 Correct 5 ms 9684 KB Output is correct
15 Correct 6 ms 9604 KB Output is correct
16 Correct 39 ms 23720 KB Output is correct
17 Correct 43 ms 23660 KB Output is correct
18 Correct 120 ms 31664 KB Output is correct
19 Correct 146 ms 35036 KB Output is correct
20 Correct 125 ms 32480 KB Output is correct
21 Correct 131 ms 32772 KB Output is correct
22 Correct 123 ms 32480 KB Output is correct
23 Correct 134 ms 34696 KB Output is correct
24 Correct 41 ms 23764 KB Output is correct
25 Correct 40 ms 23708 KB Output is correct
26 Correct 71 ms 26308 KB Output is correct
27 Correct 67 ms 26284 KB Output is correct
28 Correct 101 ms 31352 KB Output is correct
29 Correct 99 ms 31364 KB Output is correct
30 Correct 107 ms 31416 KB Output is correct
31 Correct 104 ms 31356 KB Output is correct
32 Correct 5 ms 9684 KB Output is correct
33 Correct 5 ms 9688 KB Output is correct
34 Correct 5 ms 9700 KB Output is correct
35 Correct 5 ms 9684 KB Output is correct
36 Correct 5 ms 9684 KB Output is correct
37 Correct 5 ms 9684 KB Output is correct
38 Correct 5 ms 9684 KB Output is correct
39 Correct 5 ms 9684 KB Output is correct
40 Correct 5 ms 9684 KB Output is correct
41 Correct 6 ms 9940 KB Output is correct
42 Correct 6 ms 9684 KB Output is correct
43 Correct 7 ms 9808 KB Output is correct
44 Correct 5 ms 9684 KB Output is correct
45 Correct 6 ms 9812 KB Output is correct
46 Correct 6 ms 9684 KB Output is correct
47 Correct 8 ms 9952 KB Output is correct
48 Correct 54 ms 14588 KB Output is correct
49 Correct 44 ms 14804 KB Output is correct
50 Correct 39 ms 14676 KB Output is correct
51 Correct 38 ms 14388 KB Output is correct
52 Correct 35 ms 14448 KB Output is correct
53 Correct 73 ms 19116 KB Output is correct
54 Correct 17 ms 10964 KB Output is correct
55 Correct 49 ms 13496 KB Output is correct
56 Correct 6 ms 9812 KB Output is correct
57 Correct 16 ms 10964 KB Output is correct
58 Correct 8 ms 10324 KB Output is correct
59 Correct 219 ms 31880 KB Output is correct
60 Correct 320 ms 40728 KB Output is correct
61 Correct 445 ms 59468 KB Output is correct
62 Correct 456 ms 59064 KB Output is correct
63 Correct 240 ms 42316 KB Output is correct
64 Correct 466 ms 59328 KB Output is correct
65 Correct 451 ms 59284 KB Output is correct
66 Correct 147 ms 25496 KB Output is correct
67 Correct 433 ms 52900 KB Output is correct
68 Correct 124 ms 34928 KB Output is correct
69 Correct 91 ms 27884 KB Output is correct
70 Correct 168 ms 46128 KB Output is correct
71 Correct 5 ms 9684 KB Output is correct
72 Correct 7 ms 9684 KB Output is correct
73 Correct 5 ms 9684 KB Output is correct
74 Correct 5 ms 9684 KB Output is correct
75 Correct 5 ms 9684 KB Output is correct
76 Correct 5 ms 9684 KB Output is correct
77 Correct 40 ms 23688 KB Output is correct
78 Correct 39 ms 23736 KB Output is correct
79 Correct 43 ms 23728 KB Output is correct
80 Correct 40 ms 23784 KB Output is correct
81 Correct 162 ms 36088 KB Output is correct
82 Correct 217 ms 50252 KB Output is correct
83 Correct 198 ms 50964 KB Output is correct
84 Correct 505 ms 54588 KB Output is correct
85 Correct 492 ms 55488 KB Output is correct
86 Correct 459 ms 63456 KB Output is correct
87 Correct 444 ms 65556 KB Output is correct
88 Correct 5 ms 9684 KB Output is correct
89 Correct 446 ms 65316 KB Output is correct
90 Correct 378 ms 61408 KB Output is correct
91 Correct 294 ms 56208 KB Output is correct