Submission #889444

#	Time	Username	Problem	Language	Result	Execution time	Memory
889444		winter0101	Catfish Farm (IOI22_fish)	C++17	100 / 100	301 ms	87680 KiB

fish

#include<bits/stdc++.h>
#include "fish.h"
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
const int maxn=1e5+9;
const long long inf=-1e15;
vector<int>cord[maxn];
vector<long long>a[maxn];
vector<vector<long long>>f[maxn];
vector<long long>g[maxn];
/*
f[i][j][0] col i bridge j and col i-1 bridge <=j (can update for all) to last subtask just need to count some j that j+1 have a fish
f[i][j][1] col i bridge j and col i-1 bridge >j (just can update for <=j)same as f[i][j][0]
g[i][j] col i bridge <=j and col i-1 bridge=j (just can update for >j)cal some j have fish
base f[0][0][0]=0,g[0][0]=0
*/
long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W) {
int n=N,m=M;
for1(i,0,m-1){
//a[X[i]+1][Y[i]+1]=W[i];
cord[X[i]+1].pb(Y[i]);
cord[X[i]+1].pb(Y[i]+1);
}
for1(i,0,n){
cord[i].pb(0),cord[i].pb(n);
}
for1(i,0,n){
sort(all(cord[i]));
cord[i].resize(distance(cord[i].begin(),unique(all(cord[i]))));
a[i].resize(sz(cord[i]));
f[i].resize(sz(cord[i]));
for1(j,0,sz(cord[i])-1)f[i][j].resize(2);
g[i].resize(sz(cord[i]));
for1(j,0,sz(cord[i])-1){
f[i][j][0]=f[i][j][1]=g[i][j]=inf;
}
}
f[0][0][0]=g[0][0]=0;
for1(i,0,m-1){
int pos=lower_bound(all(cord[X[i]+1]),Y[i]+1)-cord[X[i]+1].begin();
a[X[i]+1][pos]+=W[i];
}
for1(j,1,n){
for1(i,1,sz(cord[j])-1){
a[j][i]+=a[j][i-1];
}
}
for1(j,1,n){
long long bestf1=inf,bestf0=inf,bestg=inf;
int l=sz(cord[j-1]);
for2(i,sz(cord[j])-1,0){
for2(k,l-1,0){
if (cord[j-1][k]>=cord[j][i]){
int pos=upper_bound(all(cord[j]),cord[j-1][k])-cord[j].begin()-1;
bestf1=max(bestf1,f[j-1][k][1]+a[j][pos]);
bestf0=max(bestf0,f[j-1][k][0]+a[j][pos]);
bestg=max(bestg,max(f[j-1][k][0],f[j-1][k][1]));
l=k;
}
else break;
}
f[j][i][1]=max(f[j][i][1],-a[j][i]+max(bestf1,bestf0));
g[j][i]=max(g[j][i],bestg+a[j][i]);
}
l=-1;
bestf1=inf,bestf0=inf,bestg=inf;
for1(i,0,sz(cord[j])-1){
//end at cord[j][i]
int pos=upper_bound(all(cord[j-1]),cord[j][i])-cord[j-1].begin()-1;
for1(k,l+1,sz(cord[j-1])-1){
if (cord[j-1][k]<=cord[j][i]){
l=k;
bestf1=max(bestf1,f[j-1][k][1]);
bestf0=max(bestf0,f[j-1][k][0]-a[j-1][k]);
bestg=max(bestg,g[j-1][k]-a[j-1][k]);
}
else break;
}
f[j][i][0]=max(f[j][i][0],bestf1);
f[j][i][0]=max(f[j][i][0],max(bestg,bestf0)+a[j-1][pos]);
}
}
long long ans=inf;
for1(i,0,sz(cord[n])-1)ans=max({ans,f[n][i][0],f[n][i][1],g[n][i]});
return ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16