| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1125331 | VVUU | Catfish Farm (IOI22_fish) | C++20 | 0 ms | 0 KiB |
#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
long long max_weights(long long N, long long M, vector<int> X, vector<int> Y, vector<int> W){
for(long long i=0; i<M; i++) X[i]++, Y[i]++;
vector<vector<pair<long long, long long> > > p;
vector<vector<long long> > pre;
p.resize(N+10);
for(long long i=0; i<=N; i++) p[i].push_back(make_pair(0, 0));
for(long long i=0; i<M; i++) p[X[i]].push_back(make_pair(Y[i], W[i]));
vector<long long> ans;
ans.resize(N+10);
vector<vector<vector<long long> > > dp;
dp.resize(N+10);
for(long long i=1; i<=N; i++)
for(long long i=1; i<=N; i++)
for(long long i=1; i<=N; i++){
sort(p[i].begin(), p[i].end());
dp[i].resize(p[i].size(), vector<long long>(5));
pre[i].resize(p[i].size());
for(long long j=1; j<p[i].size(); j++) pre[i][j]+=pre[i][j-1]+p[i][j].second;
}
for(long long i=2; i<=N; i++){
dp[i][0][0]=dp[i-1][0][0];
long long L=p[i-1].size();
long long val=dp[i-1][L][0]+pre[i].back();
for(long long j=pre[i].size()-1; j>=0; j--){
while(L && p[i-1][L-1].first>p[i][j].first) L--, val=max(val, dp[i-1][L][0]+pre[i][j]);
if(j) dp[i][j][3]=max(dp[i][j][3], val-pre[i][j-1]);
else dp[i][j][3]=max(dp[i][j][3], val);
}
dp[i][0][0]=max(dp[i][0][0], dp[i][0][3]);
long long D=0; val=-1e18;
for(long long j=1; j<p[i].size(); j++){
dp[i][j][1]=dp[i-1][0][0];
while(D+1<p[i-1].size() && p[i-1][D+1].first<p[i][j].first){
D++; val=max(val, dp[i-1][D][2]-pre[i-1][D-1]);
}
dp[i][j][2]=max(dp[i][j][2], max(val, ans[i-2])+pre[i-1][D]);
}
ans[i]=dp[i][0][0];
for(long long j=1; j<p[i].size(); j++){
dp[i][j][0]=max(dp[i][j][1], max(dp[i][j][2], dp[i][j][3]));
ans[i]=max(ans[i], dp[i][j][0]);
}
}
return ans[N];
}