| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1289980 | MMihalev | Catfish Farm (IOI22_fish) | C++20 | 0 ms | 0 KiB |
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include "fish.h"
using namespace std;
const int MAX_N=1e5+5;
int n,m;
vector<int>x,y,w;
vector<pair<int,long long>>cells[MAX_N];//rows,weight
long long tree[4][MAX_N][3][2];
long long all,up,down,all0,up0,down0,down1;
//col , j(could be -1!), mode, pref/suf
//vector<tuple<int,int,int,int,long long>>updates[4];
void Update(int col,int pos,int mode,int prefsuf,long long val)
{
pos++;
updates.push_back({col,pos,mode,prefsuf,val})
for(;;)
{
if(pos>n)break;
tree[col][pos][mode][prefsuf]=max(tree[col][pos][mode][prefsuf],val);
pos+=((pos)&(-pos));
}
}
long long Find(int col,int pos,int mode,int prefsuf)
{
long long res=0;
pos++;
for(;;)
{
if(pos<1)break;
res=max(res,tree[col][pos][mode][prefsuf]);
pos-=((pos)&(-pos));
}
return res;
}
long long query(int col,int j,int mode,int prefsuf)
{
if(prefsuf==0)
{
return Find(col,j,mode,prefsuf);
}
j=n-1-j;
return Find(col,j,mode,prefsuf);
}
void transition(int i,int j)
{
if(j==-1)return;
long long ans=0;
up=all-down;
up0=all0-down0;
ans=down0;
if(i-1>=0)
{ans=max(ans,query(0,j,0,0)-up0);
ans=max(ans,query(0,j,1,1)-down);}
if(i-2>=0)
{ans=max(ans,query(1,j,2,0)+down0);
ans=max(ans,query(1,j,1,1));}
if(i-3>=0)
{ans=max(ans,query(2,n-1,1,0)+down0);}
Update(3,j,0,0,ans+up);
Update(3,n-1-j,0,1,ans+up);
if(i+1<n)
{Update(3,j,1,0,ans+down1);
Update(3,n-1-j,1,1,ans+down1);}
Update(3,j,2,0,ans);
Update(3,n-1-j,2,1,ans);
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W)
{
n=N;
m=M;
x=X;
y=Y;
w=W;
for(int i=0;i<m;i++)
{
cells[x[i]].push_back({y[i],w[i]});
}
for(int i=0;i<n;i++)
{
sort(cells[i].begin(),cells[i].end());
}
long long ans=0;
for(int i=0;i<n;i++)
{
all=0;up=0;down=0;
all0=0;up0=0;down0=0;
down1=0;
for(auto [row,price]:cells[i])all+=price;
if(i-1>=0)for(auto [row,price]:cells[i-1])all0+=price;
int id0=0;
int id1=0;
int prow=-1;
for(auto [row,price]:cells[i])
{
while(i-1>=0 && id0<cells[i-1].size() && cells[i-1][id0].first<row)
{
down0+=cells[i-1][id0].second;
id0++;
}
while(i+1<n && id1<cells[i+1].size() && cells[i+1][id1].first<row)
{
down1+=cells[i+1][id1].second;
id1++;
}
if(row-1>prow)transition(i,row-1);
while(i-1>=0 && id0<cells[i-1].size() && cells[i-1][id0].first<=row)
{
down0+=cells[i-1][id0].second;
id0++;
}
while(i+1<n && id1<cells[i+1].size() && cells[i+1][id1].first<=row)
{
down1+=cells[i+1][id1].second;
id1++;
}
down+=price;
transition(i,row);
prow=row;
}
while(i-1>=0 && id0<cells[i-1].size() && cells[i-1][id0].first<=n-1)
{
down0+=cells[i-1][id0].second;
id0++;
}
while(i+1<n && id1<cells[i+1].size() && cells[i+1][id1].first<=n-1)
{
down1+=cells[i+1][id1].second;
id1++;
}
transition(i,n-1);
swap(tree[3],tree[0]);
swap(tree[3],tree[1]);
swap(tree[3],tree[2]);
if(i==1)
{
//cout<<query(0,2,0,0)<<"\n";
}
memset(tree[3],0,sizeof(tree[3]));
}
ans=max(ans,Find(0,n-1,2,0));
ans=max(ans,Find(1,n-1,1,0));
if(n>=3)ans=max(ans,Find(2,n-1,1,0));
return ans;
}