| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 629822 | Vovamatrix | 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.
//https://oj.uz/problem/view/IOI22_fish
#include "fish.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define sc second
#define th third
#define fo fourth
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
#define endl "\n"
#define all(data) data.begin(),data.end()
#define TYPEMAX(type) std::numeric_limits<type>::max()
#define TYPEMIN(type) std::numeric_limits<type>::min()
#define ima_li_te(D,d) find(all(D),d)
#define MAXN 100007
#define MAXM 300007
ll dp[2][3][MAXN];
ll sol(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
vector<pii> v[n];
ll cnt=0;
for(int i=0;i<m;i++) y[i]++;
for(int i=0;i<m;i++) v[x[i]].pb(mp(y[i],w[i]));
for(int i=0;i<n;i++)
{
v[i].pb(mp(0,0)); sort(all(v[i])); v[i].pb(mp(n+2,0));
for(int j=1;j<v[i].size();j++) v[i][j].sc+=v[i][j-1].sc;
}
for(int i=0;i<v[1].size();i++)
{
ll k=0;
while(k+1<v[0].size() && v[1][i].fi>v[0][k+1].fi) k++;
dp[1][2][i]=v[1].back().sc-v[1][max(i-1,0)].sc;
dp[1][1][i]=v[0][k].sc;
}
for(int i=0;i<v[0].size();i++)
{
ll k=0;
while(k+1<v[1].size() && v[0][i].fi>v[1][k+1].fi) k++;
dp[1][0][i]=v[1][k].sc;
}
for(int i=2;i<n;i++)
{
for(int j=0;j<3;j++)
{
for(int k=0;k<max(v[i-1].size(),v[i].size());k++) dp[i&1][j][k]=0;
}
for(int j=0;j<v[i-1].size();j++)
{
ll k=0;
while(k+1<v[i].size() && v[i-1][j].fi>v[i][k+1].fi) k++;
dp[i&1][0][j]=max(dp[(i&1)^1][1][j],dp[(i&1)^1][2][j])+v[i][k].sc;
}
cnt=-1;
for(int j=0;j<v[i].size();j++)
{
ll k=0,l=0,p=0;
while(k<v[i-2].size() && v[i][j].fi>v[i-2][k].fi)
{
while(l<v[i-1].size()-1 && v[i-2][k].fi>v[i-1][l+1].fi) l++;
cnt=max(cnt,dp[(i&1)^1][0][k]+v[i-1][l].sc);
k++;
}
while(p<v[i-1].size()-1 && v[i][j].fi>v[i-1][p+1].fi) p++;
dp[i&1][1][j]=max(dp[i&1][1][j],cnt-v[i-1][p].sc);
}
cnt=-1;
for(int j=v[i].size()-1;j>=0;j--)
{
ll k=v[i-2].size()-1;
while(k>=0 && v[i][j].fi<=v[i-2][k].fi)
{
cnt=max(cnt,dp[(i&1)^1][0][k]);
k--;
}
dp[i&1][1][j]=max(dp[i&1][1][j],cnt);
}
cnt=-1;
for(int j=0;j<v[i].size();j++)
{
ll k=0,l=0;
while(k<v[i-1].size() && v[i][j].fi>=v[i-1][k].fi)
{
cnt=max(cnt, dp[(i&1)^1][1][k]-v[i-1][max(k-1,0ll)].sc);
k++;
}
while(l<v[i-1].size()-1 && v[i][j].fi > v[i-1][l].fi) l++;
dp[i&1][1][j]=max(dp[i&1][1][j],cnt+v[i-1][max(l-1,0ll)].sc);
}
cnt=-1;
for(int j=v[i].size()-1;j>=0;j--)
{
ll k=v[i-1].size()-1,l=v[i].size()-1;
while(k>=0 && v[i][j].fi<v[i-1][k].fi)
{
while(l>0 && v[i-1][k].fi<=v[i][l].fi) l--;
cnt=max(cnt,max(dp[(i&1)^1][1][k],dp[(i&1)^1][2][k])+v[i][l].sc);
k--;
}
dp[i&1][2][j]=max(dp[i&1][2][j],cnt-v[i][max(j-1,0)].sc);
}
}
ll rez=0;
for(int i=0;i<v[n-2].size();i++) rez=max(rez,dp[(n-1)&1][0][i]);
for(int i=1;i<3;i++)
{
for(int j=0;j<v[n-1].size();j++) rez=max(rez,dp[(n-1)&1][i][j]);
}
return rez;
}