#include <iostream>
#include <utility>
#include <vector>
#include <algorithm>
#include <limits>
#include <cstring>
#define NN 100005
std::vector<std::pair<int, int64_t>> weight[NN];
std::vector<std::pair<int, int64_t>> dp_left[NN];
std::vector<std::pair<int, int64_t>> dp_right[NN];
void printWeight(int n, int m) {
for (int i = 0; i < n; ++i) {
std::cout << i << " -> ";
for (int j = 0; j < weight[i].size(); ++j) {
std::cout << "(" << weight[i][j].first << ", " << weight[i][j].second << ") ";
}
std::cout << std::endl;
}
}
void printDp(int n, int m) {
std::cout << "======= dp_left =======" << std::endl;
for (int i = 0; i < n; ++i) {
std::cout << i << " -> ";
for (int j = 0; j < dp_left[i].size(); ++j) {
std::cout << "(" << dp_left[i][j].first << ", " << dp_left[i][j].second << ") ";
}
std::cout << std::endl;
}
std::cout << "======= dp_right =======" << std::endl;
for (int i = 0; i < n; ++i) {
std::cout << i << " -> ";
for (int j = 0; j < dp_right[i].size(); ++j) {
std::cout << "(" << dp_right[i][j].first << ", " << dp_right[i][j].second << ") ";
}
std::cout << std::endl;
}
}
int64_t binarySearchWeight(int i, int h) {
if (weight[i].size() == 0) {
return 0;
}
auto iter = std::upper_bound(weight[i].begin(), weight[i].end(), std::make_pair(h, std::numeric_limits<int64_t>::max()));
if (iter == weight[i].begin()) {
return 0;
}
--iter;
return iter->second;
}
void printBinarySearchResult() {
int64_t ret;
ret = binarySearchWeight(3, 2);
std::cout << "binary search (3, 2) -> " << ret << std::endl;
ret = binarySearchWeight(3, 3);
std::cout << "binary search (3, 3) -> " << ret << std::endl;
ret = binarySearchWeight(3, 4);
std::cout << "binary search (3, 4) -> " << ret << std::endl;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
int n = N, m = M;
for (int i = 0; i < m; ++i) {
weight[X[i]].push_back(std::make_pair(Y[i], W[i]));
}
for (int i = 0; i < n; ++i) {
std::sort(weight[i].begin(), weight[i].end());
// 计算前缀和
for (int j = 1; j < weight[i].size(); ++j) {
weight[i][j].second += weight[i][j - 1].second;
}
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < weight[i].size(); ++j) {
int h = weight[i][j].first - 1;
dp_left[i].push_back(std::make_pair(h, 0));
dp_right[i].push_back(std::make_pair(h, 0));
}
dp_left[i].push_back(std::make_pair(n - 1, 0));
dp_right[i].push_back(std::make_pair(n - 1, 0));
}
// left
int64_t temp = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < dp_left[i].size(); ++j) {
for (int k = 0; k < dp_left[i - 1].size() && i > 0; ++k) {
int64_t add_weight = 0;
if (dp_left[i - 1][k].first < dp_left[i][j].first) {
add_weight = binarySearchWeight(i - 1, dp_left[i][j].first) - binarySearchWeight(i - 1, dp_left[i - 1][k].first);
} else {
if (temp > dp_left[i][j].second) {
dp_left[i][j].second = temp;
}
break;
}
dp_left[i][j].second = std::max(dp_left[i - 1][k].second + add_weight, dp_left[i][j].second);
}
}
temp = 0;
for (int j = 0; j < dp_left[i].size(); ++j) {
temp = std::max(temp, dp_left[i][j].second);
}
}
// right
temp = 0;
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j < dp_right[i].size(); ++j) {
for (int k = 0; k < dp_right[i + 1].size() && i < n - 1; ++k) {
int64_t add_weight = 0;
if (dp_right[i + 1][k].first < dp_right[i][j].first) {
add_weight = binarySearchWeight(i + 1, dp_right[i][j].first) - binarySearchWeight(i + 1, dp_right[i + 1][k].first);
} else {
if (temp > dp_right[i][j].second) {
dp_right[i][j].second = temp;
}
break;
}
dp_right[i][j].second = std::max(dp_right[i + 1][k].second + add_weight, dp_right[i][j].second);
}
}
temp = 0;
for (int j = 0; j < dp_right[i].size(); ++j) {
temp = std::max(temp, dp_right[i][j].second);
}
}
// result
int64_t result = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < dp_left[i].size(); ++j) {
if (dp_left[i][j].second + dp_right[i][j].second > result) {
result = dp_left[i][j].second + dp_right[i][j].second;
}
}
}
return result;
}
int test_main() {
int n, m;
std::cin >> n >> m;
for (int i = 0; i < m; ++i) {
int x, y, w;
std::cin >> x >> y >> w;
weight[x].push_back(std::make_pair(y, w));
}
for (int i = 0; i < n; ++i) {
std::sort(weight[i].begin(), weight[i].end());
// 计算前缀和
for (int j = 1; j < weight[i].size(); ++j) {
weight[i][j].second += weight[i][j - 1].second;
}
}
// printWeight(n, m);
// printBinarySearchResult();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < weight[i].size(); ++j) {
int h = weight[i][j].first - 1;
dp_left[i].push_back(std::make_pair(h, 0));
dp_right[i].push_back(std::make_pair(h, 0));
}
dp_left[i].push_back(std::make_pair(n - 1, 0));
dp_right[i].push_back(std::make_pair(n - 1, 0));
}
// left
int64_t temp = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < dp_left[i].size(); ++j) {
for (int k = 0; k < dp_left[i - 1].size() && i > 0; ++k) {
int64_t add_weight = 0;
if (dp_left[i - 1][k].first < dp_left[i][j].first) {
add_weight = binarySearchWeight(i - 1, dp_left[i][j].first) - binarySearchWeight(i - 1, dp_left[i - 1][k].first);
} else {
if (dp_left[i][j].second >= temp) {
break;
}
}
dp_left[i][j].second = std::max(dp_left[i - 1][k].second + add_weight, dp_left[i][j].second);
}
}
temp = 0;
for (int j = 0; j < dp_left[i - 1].size() && i > 0; ++j) {
temp = std::max(temp, dp_left[i - 1][j].second);
}
}
// right
temp = 0;
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j < dp_right[i].size(); ++j) {
for (int k = 0; k < dp_right[i + 1].size() && i < n - 1; ++k) {
int64_t add_weight = 0;
if (dp_right[i + 1][k].first < dp_right[i][j].first) {
add_weight = binarySearchWeight(i + 1, dp_right[i][j].first) - binarySearchWeight(i + 1, dp_right[i + 1][k].first);
} else {
if (dp_right[i][j].second >= temp) {
break;
}
}
dp_right[i][j].second = std::max(dp_right[i + 1][k].second + add_weight, dp_right[i][j].second);
}
}
temp = 0;
for (int j = 0; j < dp_left[i + 1].size() && i < n - 1; ++j) {
temp = std::max(temp, dp_left[i + 1][j].second);
}
}
// printDp(n, m);
// result
int64_t result = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < dp_left[i].size(); ++j) {
if (dp_left[i][j].second + dp_right[i][j].second > result) {
result = dp_left[i][j].second + dp_right[i][j].second;
}
}
}
std::cout << result << std::endl;
return 0;
}
Compilation message
fish.cpp: In function 'void printWeight(int, int)':
fish.cpp:17:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for (int j = 0; j < weight[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp: In function 'void printDp(int, int)':
fish.cpp:28:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (int j = 0; j < dp_left[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:36:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for (int j = 0; j < dp_right[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for (int j = 1; j < weight[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | for (int j = 0; j < weight[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp:94:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | for (int j = 0; j < dp_left[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:95:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for (int k = 0; k < dp_left[i - 1].size() && i > 0; ++k) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:109:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | for (int j = 0; j < dp_left[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:117:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
117 | for (int j = 0; j < dp_right[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:118:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for (int k = 0; k < dp_right[i + 1].size() && i < n - 1; ++k) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:132:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
132 | for (int j = 0; j < dp_right[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:140:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
140 | for (int j = 0; j < dp_left[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~
fish.cpp: In function 'int test_main()':
fish.cpp:161:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | for (int j = 1; j < weight[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp:169:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
169 | for (int j = 0; j < weight[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp:181:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
181 | for (int j = 0; j < dp_left[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~
fish.cpp:182:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
182 | for (int k = 0; k < dp_left[i - 1].size() && i > 0; ++k) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:195:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for (int j = 0; j < dp_left[i - 1].size() && i > 0; ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:203:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
203 | for (int j = 0; j < dp_right[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:204:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
204 | for (int k = 0; k < dp_right[i + 1].size() && i < n - 1; ++k) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:217:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
217 | for (int j = 0; j < dp_left[i + 1].size() && i < n - 1; ++j) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:227:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
227 | for (int j = 0; j < dp_left[i].size(); ++j) {
| ~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
19456 KB |
Output is correct |
| 2 |
Correct |
64 ms |
21168 KB |
Output is correct |
| 3 |
Correct |
16 ms |
13524 KB |
Output is correct |
| 4 |
Correct |
16 ms |
13580 KB |
Output is correct |
| 5 |
Correct |
194 ms |
37812 KB |
Output is correct |
| 6 |
Correct |
194 ms |
44796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 2 |
Execution timed out |
1085 ms |
26080 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
13524 KB |
Output is correct |
| 2 |
Correct |
17 ms |
13604 KB |
Output is correct |
| 3 |
Incorrect |
46 ms |
17580 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
7380 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '165109154345' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
7380 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '165109154345' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 2 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 3 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 4 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 5 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 6 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7380 KB |
Output is correct |
| 8 |
Correct |
4 ms |
7252 KB |
Output is correct |
| 9 |
Incorrect |
4 ms |
7380 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '165109154345' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
17 ms |
13524 KB |
Output is correct |
| 2 |
Correct |
17 ms |
13604 KB |
Output is correct |
| 3 |
Incorrect |
46 ms |
17580 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '16359027219341' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
53 ms |
19456 KB |
Output is correct |
| 2 |
Correct |
64 ms |
21168 KB |
Output is correct |
| 3 |
Correct |
16 ms |
13524 KB |
Output is correct |
| 4 |
Correct |
16 ms |
13580 KB |
Output is correct |
| 5 |
Correct |
194 ms |
37812 KB |
Output is correct |
| 6 |
Correct |
194 ms |
44796 KB |
Output is correct |
| 7 |
Correct |
5 ms |
7252 KB |
Output is correct |
| 8 |
Execution timed out |
1085 ms |
26080 KB |
Time limit exceeded |
| 9 |
Halted |
0 ms |
0 KB |
- |
