| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 632653 | stefanlin | 메기 농장 (IOI22_fish) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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
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);
}
}
}
// result
long long result = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < dp_left[i].size(); ++j) {
result = std::max(dp_left[i][j].second + dp_right[i][j].second, result);
}
}
return result;
}
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;
}