| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 807273 | I_Love_EliskaM_ | Catfish Farm (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;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;
#define pi pair<ll,ll>
#define f first
#define s second
const int N=7005;
ll dp[N][N];
ll dp2[N][N];
ll dp3[N][N];
ll pr[N][N];
ll prmx[N][N];
ll prmx2[N][N];
ll sfmx[N][N];
ll good(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
forn(i,n+2) forn(j,n+2) dp[i][j]=dp2[i][j]=dp3[i][j]=pr[i][j]=prmx2[i][j]=prmx[i][j]=sfmx[i][j]=0;
if (n>N) exit(0);
forn(i,m) {
pr[x[i]+1][y[i]+1]=w[i];
}
forn(i,n) {
forn(j,n) {
pr[i+1][j+1]+=pr[i+1][j];
}
}
for (int i=1; i<=n; ++i) {
for (int j=0; j<=n; ++j) {
if (i>=2) {
dp[i][j]=max(dp[i][j],prmx[i-2][j]+pr[i-1][j]);
dp[i][j]=max(dp[i][j],sfmx[i-2][j]);
}
dp[i][j]=max(dp[i][j],prmx2[i-1][j]+pr[i-1][j]);
dp[i][j]=max(dp[i][j],prmx[i-1][j]);
dp3[i][j]=dp[i][j];
dp[i][j]=max(dp[i][j],sfmx[i-1][j]-pr[i][j]);
dp2[i][j] = dp[i][j]+pr[i+1][j];
}
prmx[i][0]=dp[i][0];
for (int j=1; j<=n; ++j) prmx[i][j]=max(dp[i][j],prmx[i][j-1]);
sfmx[i][n]=dp2[i][n];
for (int j=n-1; j>=0; --j) sfmx[i][j]=max(dp2[i][j],sfmx[i][j+1]);
prmx2[i][0]=dp3[i][0];
for (int j=1; j<=n; ++j) prmx2[i][j]=max(dp3[i][j]-pr[i][j],prmx2[i][j-1]);
}
ll ans=0;
for (int j=0; j<=n; ++j) ans=max(ans,dp[n][j]);
return ans;
}
const int _N=100005;
vector<ll> _pr[_N];
vector<pi> f[_N];
ll sum(int i, int j) {
int l=0, r=f[i].size();
while (l<r) {
int m=(l+r+1)>>1;
if (f[i][m-1].f>j) r=m-1;
else l=m;
}
return _pr[i][r];
}
vector<pi> _dp[_N], _dp2[_N], _dp3[_N];
vector<ll> _prmx[_N], _prmx2[_N], _sfmx[_N];
ll _prmxquery(int i, int j) {
int l=0, r=_dp[i].size();
while (l<r) {
int m=(l+r+1)>>1;
if (_dp[i][m-1].f > j) r=m-1;
else l=m;
}
return _prmx[i][r];
}
ll _prmx2query(int i, int j) {
int l=0, r=_dp3[i].size();
while (l<r) {
int m=(l+r+1)>>1;
if (_dp3[i][m-1].f > j) r=m-1;
else l=m;
}
return _prmx2[i][r];
}
ll _sfmxquery(int i, int j) {
int l=0, r=_dp2[i].size();
while (l<r) {
int m=(l+r)>>1;
if (_dp2[i][m].f<j) l=m+1;
else r=m;
}
return _sfmx[i][r];
}
ll bad(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
forn(i,m) {
f[x[i]+1].pb({y[i]+1,w[i]});
}
for(int i=1;i<=n;++i) {
sort(all(f[i]));
f[i].pb({n+1,0});
_pr[i]={0};
forn(j,f[i].size()) _pr[i].pb(_pr[i].back()+f[i][j].s);
}
_dp[0].pb({0,0});
_dp[0].pb({n,0});
_pr[0]={0,0,0};
_dp2[0]=_dp3[0]=_dp[0];
_prmx[0]={0,0};
_prmx2[0]=_sfmx[0]=_prmx[0];
_pr[n+1]={0,0,0};
for(int i=1; i<=n; ++i) {
for(auto&x:f[i]) {
int j=x.f-1;
ll d=0;
if (i>=2) {
d=max(d,_prmxquery(i-2,j)+sum(i-1,j));
d=max(d,_sfmxquery(i-2,j));
}
d=max(d,_prmx2query(i-1,j)+sum(i-1,j));
d=max(d,_prmxquery(i-1,j));
ll d3=d;
d=max(d,_sfmxquery(i-1,j)-sum(i,j));
ll d2=d+sum(i+1,j);
_dp[i].pb({j,d});
_dp2[i].pb({j,d2});
_dp3[i].pb({j,d3});
}
_prmx[i]={0};
_prmx2[i]=_sfmx[i]=_prmx[i];
for (int j=0; j<_dp[i].size(); ++j) {
_prmx[i].pb(max(_prmx[i].back(),_dp[i][j].s));
_prmx2[i].pb(max(_prmx2[i].back(),_dp3[i][j].s-sum(i,_dp3[i][j].f)));
}
reverse(all(_dp2[i]));
for (int j=0; j<_dp2[i].size(); ++j) {
_sfmx[i].pb(max(_sfmx[i].back(),_dp2[i][j].s));
}
reverse(all(_dp2[i]));
reverse(all(_sfmx[i]));
}
ll ans=0;
for(auto&x:_dp) for(auto&y:x) ans=max(ans,y.s);
for (int i=0; i<=n+1; ++i) {
_dp[i].clear();
_dp2[i].clear();
_dp3[i].clear();
_prmx[i].clear();
_pr[i].clear();
_prmx2[i].clear();
_sfmx[i].clear();
f[i].clear();
}
return ans;
}
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
if (n<=N) return good(n,m,x,y,w);
return bad(n,m,x,y,w);
}