| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 713156 | t6twotwo | 메기 농장 (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 "fish.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int64_t>> solve(vector<vector<int>> &pos, vector<vector<array<int, 2>>> &w) {
int N = pos.size() - 1;
vector<vector<int64_t>> dp(N + 1);
dp[0].push_back(0);
for (int i = 1; i <= N; i++) {
int M = pos[i].size();
dp[i].resize(M);
int64_t mx = 0;
for (int j = 0, k = 0, l = 0, r = 0; j < M; j++) {
while (k < pos[i - 1].size() && pos[i - 1][k] <= pos[i][j]) {
if (dp[i - 1][k] > mx) {
while (l < w[i - 1].size() && w[i - 1][l][0] <= pos[i - 1][k]) l++;
mx = dp[i - 1][k];
}
k++;
}
while (r < w[i - 1].size() && w[i - 1][r][0] <= pos[i][j]) mx += w[i - 1][r++][1];
dp[i][j] = mx;
}
}
return dp;
}
int64_t max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<array<int, 2>>> w(N + 1);
for (int i = 0; i < M; i++) {
w[X[i] + 1].push_back({Y[i], W[i]});
}
vector pos(N + 1, vector<int>{-1});
for (int i = 1; i <= N; i++) {
sort(w[i].begin(), w[i].end());
for (auto [x, _] : w[i]) {
if (i > 1) pos[i - 1].push_back(x);
if (i < N) pos[i + 1].push_back(x);
}
}
for (int i = 1; i <= N; i++) {
sort(pos[i].begin(), pos[i].end());
}
auto dp1 = solve(pos, w);
reverse(pos.begin() + 1, pos.end());
reverse(w.begin() + 1, w.end());
auto dp2 = solve(pos, w);
int64_t ans = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < pos[i + 1].size(); j++) {
ans = max(ans, dp1[N - i][j] + dp2[i + 1][j]);
}
}
return ans;
}