| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 632655 | stefanlin | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
int 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
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);
}
dp_left[i][j].second = std::max(dp_left[i - 1][k].second + add_weight, dp_left[i][j].second);
}
}
}
// right
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);
}
dp_right[i][j].second = std::max(dp_right[i + 1][k].second + add_weight, dp_right[i][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;
}