| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1127012 | bruh | Catfish Farm (IOI22_fish) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define int long long
#define all(x) x.begin(), x.end()
using namespace std;
const int maxn = 3e5 + 5;
int n, m, ans;
array<int, 3> a[maxn];
inline void MAX(int &a, int b)
{
a = max(a, b);
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("CATFISH.inp", "r", stdin);
// freopen("CATFISH.out", "w", stdout);
cin >> n >> m;
int sub1 = 1, sub2 = 1, sub3 = 1;
for (int i = 1; i <= m; i++)
{
cin >> a[i][0] >> a[i][1] >> a[i][2];
sub1 &= a[i][0] % 2 == 0;
sub2 &= a[i][0] <= 1;
sub3 &= a[i][1] == 0;
}
if (sub1)
{
int ans = 0;
for (int i = 1; i <= m; i++)
ans += a[i][2];
cout << ans;
} else if (sub2)
{
vector<pair<int,int>> val[2];
for (int i = 1; i <= m; i++)
val[a[i][0]].emplace_back(a[i][1], a[i][2]);
sort(all(val[0]));
sort(all(val[1]));
vector<int> pf[2];
pf[0].assign(n + 5, 0);
pf[1].assign(n + 5, 0);
for (int i = 1; i <= val[0].size(); i++)
pf[0][i] = pf[0][i - 1] + val[0][i - 1].second;
for (int i = 1; i <= val[1].size(); i++)
pf[1][i] = pf[1][i - 1] + val[1][i - 1].second;
int ans = max(pf[0][val[0].size()], pf[1][val[1].size()]);
for (int i = 1, pt = -1; i <= val[1].size(); i++)
{
int height = val[1][i - 1].first - 1;
int cur = (n > 2 ? pf[1][val[1].size()] - pf[1][i - 1] : 0);
while (pt + 1 < val[0].size() && val[0][pt + 1].first <= height)
pt++;
cur += pf[0][pt + 1];
ans = max(ans, cur);
}
for (int i = 1, pt = -1; i <= val[0].size(); i++)
{
int height = val[0][i - 1].first - 1;
int cur = 0;
while (pt + 1 < val[1].size() && val[1][pt + 1].first <= height)
pt++;
cur += pf[1][pt + 1];
ans = max(ans, cur);
}
cout << ans;
} else if (sub3)
{
vector<int> b(n + 10, 0), dp(n + 10, 0);
for (int i = 1; i <= m; i++)
b[a[i][0] + 1] = a[i][2];
int ans = 0;
for (int i = 1; i <= n; i++)
{
/// choose i
dp[i] = b[i - 1] + b[i + 1];
for (int j = 3; j <= 50; j++) if (i - j >= 1)
dp[i] = max(dp[i], dp[i - j] + b[i + 1] + b[i - 1]);
else break;
if (i >= 2)
dp[i] = max(dp[i], dp[i - 1] - b[i] + b[i + 1]);
if (i >= 3)
dp[i] = max(dp[i], dp[i - 2] + b[i + 1]);
ans = max(ans, dp[i]);
}
cout << ans;
} else
{
vector<vector<int>> b(n + 10, vector<int>(n + 10, 0));
int mx = 0;
for (int i = 1; i <= m; i++)
b[a[i][0] + 1][a[i][1] + 1] = a[i][2],
mx = max(mx, a[i][1] + 1);
vector<vector<int>> pf(n + 10, vector<int>(mx + 2, 0));
vector<vector<vector<int>>> dp(2, vector<vector<int>>(mx + 1, vector<int>(mx + 2, 0)));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= mx; j++)
pf[i][j] = pf[i][j - 1] + b[i][j];
}
for (int j = 0; j <= mx; j++) for (int i = 0; i <= mx; i++)
dp[0][i][j] = -1e18;
dp[0][0][0] = 0;
int be = 0, cu = 1;
for (int i = 1; i <= n + 2; i++)
{
for (int u = 0; u <= mx; u++) for (int v = 0; v <= mx; v++)
dp[cu][u][v] = -1e18;
for (int pre = 0; pre <= mx; pre++)
for (int now = 0; now <= mx; now++) if (dp[be][pre][now] != -1e18)
for (int nxt = 0; nxt <= mx; nxt++)
{
if (now >= nxt)
{
MAX(dp[cu][now][nxt], dp[be][pre][now] + pf[i][now] - pf[i][nxt]);
} else
{
if (nxt >= max(pre, now))
MAX(dp[cu][now][nxt], dp[be][pre][now] + pf[i - 1][nxt] - pf[i - 1][max(pre, now)]);
}
}
swap(be, cu);
// for (int u = 0; u <= n; u++) for (int v = 0; v <= n; v++)
// if (dp[be][u][v] != -1e18)
// cout << i << " " << u << " " << v << " " << dp[be][u][v] << " ?\n";
}
cout << dp[be][0][0];
}
}