| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1168505 | jj_master | Catfish Farm (IOI22_fish) | C++20 | 0 ms | 0 KiB |
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
int max_weights(int N, int M, vector<int> &X, vector<int> &Y, vector<int> &W)
{
// Initialize DP, pref, sp, t1, t2, t3, t4
vector<vector<long long>> DP(N + 1, vector<long long>(2, 0ll));
vector<vector<pair<int, long long>>> pref(N + 2);
for (int i = 0; i <= N + 1; i++) pref[i].emplace_back(0, 0);
vector<vector<int>> sp(N + 2);
for (int i = 1; i <= N + 1; i++) sp[i].emplace_back(0);
for (int i = 1; i <= N + 1; i++) sp[i].emplace_back(N);
vector<vector<long long>> t1(2, vector<long long>(N + 1, 0ll));
vector<vector<long long>> t2(3, vector<long long>(N + 1, 0ll));
vector<vector<long long>> t3(3, vector<long long>(N + 1, 0ll));
vector<vector<long long>> t4(2, vector<long long>(N + 1, 0ll));
// Populate the pref and sp arrays
for (int i = 0; i < M; i++) {
pref[X[i] + 1].emplace_back(Y[i] + 1, W[i]);
sp[X[i] + 1].emplace_back(Y[i]);
}
// Sort and process the pref and sp arrays
for (int i = 1; i <= N + 1; i++) {
sort(sp[i].begin(), sp[i].end());
sp[i].erase(unique(sp[i].begin(), sp[i].end()), sp[i].end());
sort(pref[i].begin(), pref[i].end());
for (int j = 1; j < pref[i].size(); j++) pref[i][j].second += pref[i][j - 1].second;
}
// Lambda functions to get prefix sum and find boundaries
auto getpref = [&](int i, int j) {
auto iter = lower_bound(pref[i].begin(), pref[i].end(), make_pair(j + 1, -1ll));
iter--;
return iter->second;
};
auto get_higher = [&](int i, int j) {
return lower_bound(sp[i].begin(), sp[i].end(), j) - sp[i].begin() - 0;
};
auto get_lower = [&](int i, int j) {
return upper_bound(sp[i].begin(), sp[i].end(), j) - sp[i].begin() - 1;
};
// Main logic for DP
for (int i = 2; i <= N; i++) {
int tot = sp[i].size() - 1;
for (int s = 0; s <= tot; s++) {
int j = sp[i][s];
if (i != 2) DP[s][1] = max(DP[s][1], -getpref(i, j) + t1[0][get_higher(i - 1, j)]);
else DP[s][1] = max(DP[s][1], getpref(i, N) - getpref(i, j));
if (i > 2) {
if (i != 3) {
DP[s][0] = max(DP[s][0], getpref(i - 1, j) + t2[0][get_lower(i - 2, j)]);
DP[s][0] = max(DP[s][0], t3[0][get_higher(i - 2, j)]);
} else DP[s][0] = max(DP[s][0], getpref(i - 1, N));
}
if (i != 2) DP[s][0] = max(DP[s][0], getpref(i - 1, j) + t4[0][get_lower(i - 1, j)]);
else DP[s][0] = max(DP[s][0], getpref(i - 1, j));
t1[1][s] = getpref(i + 1, j) + max(DP[s][0], DP[s][1]);
t2[2][s] = max(DP[s][0], DP[s][1]);
t3[2][s] = getpref(i + 1, j) + max(DP[s][0], DP[s][1]);
t4[1][s] = -getpref(i, j) + DP[s][0];
}
// Update the t1, t2, t3, t4 vectors
for (int j = tot - 1; j >= 0; j--) t1[1][j] = max(t1[1][j], t1[1][j + 1]);
for (int j = 1; j <= tot; j++) t2[2][j] = max(t2[2][j], t2[2][j - 1]);
for (int j = tot - 1; j >= 0; j--) t3[2][j] = max(t3[2][j], t3[2][j + 1]);
for (int j = 1; j <= tot; j++) t4[1][j] = max(t4[1][j], t4[1][j - 1]);
// Swap to prepare for the next iteration
swap(t1[0], t1[1]);
swap(t2[0], t2[1]);
swap(t2[1], t2[2]);
swap(t3[0], t3[1]);
swap(t3[1], t3[2]);
swap(t4[0], t4[1]);
}
// Find the maximum value from the DP array
long long ans = 0;
for (int j = 0; j <= N; j++) ans = max(ans, DP[j][0]);
for (int j = 0; j <= N; j++) ans = max(ans, DP[j][1]);
return ans;
}