Submission #725674

#	Time	Username	Problem	Language	Result	Execution time	Memory
725674		Urvuk3	Catfish Farm (IOI22_fish)	C++17	0 / 100	296 ms	36416 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const int INF=1e9;
const ll LINF=1e18;
#define fi first
#define se second
#define pii pair<int,int>
#define mid ((l+r)/2)
#define sz(a) (int((a).size()))
#define all(a) a.begin(),a.end()
#define endl "\n"
#define pb push_back

void PRINT(int x) {cerr << x;}
void PRINT(ll x) {cerr << x;}
void PRINT(double x) {cerr << x;}
void PRINT(char x) {cerr << '\'' << x << '\'';}
void PRINT(string x) {cerr << '\"' << x << '\"';}
void PRINT(bool x) {cerr << (x ? "true" : "false");}

template<typename T,typename V>
void PRINT(pair<T,V>& x){
    cerr<<"{";
    PRINT(x.fi);
    cerr<<",";
    PRINT(x.se);
    cerr<<"}";
}
template<typename T>
void PRINT(T &x){
    int id=0;
    cerr<<"{";
    for(auto _i:x){
        cerr<<(id++ ? "," : "");
        PRINT(_i);
    }
    cerr<<"}";
}
void _PRINT(){
    cerr<<"]\n";
}
template<typename Head,typename... Tail>
void _PRINT(Head h,Tail... t){
    PRINT(h);
    if(sizeof...(t)) cerr<<", ";
    _PRINT(t...);
}

#define Debug(x...) cerr<<"["<<#x<<"]=["; _PRINT(x)

vector<vector<int>> ind;
vector<vector<pair<int,ll>>> fish;
vector<vector<ll>> dp[2];
map<int,ll> pref;

ll Sum(int l,int r){
    ll prefr=prev(pref.upper_bound(r))->se;
    ll prefl=prev(pref.upper_bound(l-1))->se;
    return prefr-prefl;
}

void MaxSelf(ll& x,ll y){
    x=max(x,y);
}

long long max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W){
    ind.resize(N); fish.resize(N);
    dp[0].resize(N); dp[1].resize(N);
    for(int i=0;i<M;i++){
        if(X[i]) ind[X[i]-1].pb(Y[i]+1);
        if(X[i]+1<N) ind[X[i]+1].pb(Y[i]+1);
        fish[X[i]].pb({Y[i],W[i]});
    }
    for(int i=0;i<N;i++){
        ind[i].pb(0);
        ind[i].pb(N);
        sort(all(ind[i]));
        ind.resize(unique(all(ind))-ind.begin());
        dp[0][i].resize(sz(ind[i]));
        dp[1][i].resize(sz(ind[i]));
    }
    for(int x=1;x<N;x++){
        pref.clear(); pref[-1]=0;
        for(int i=0;i<sz(fish[x-1]);i++){
            int y=fish[x-1][i].fi;
            int w=fish[x-1][i].se;
            pref[y]=pref.upper_bound(y-1)->se+w;
        }
        if(x>1){
            int i1=sz(ind[x-2])-1;
            ll suf_max=-LINF;
            for(int i=sz(ind[x])-1;i>=0;i--){
                while(i1>=0 && ind[x-2][i1]>ind[x][i]){
                    ll m=max(dp[0][x-2][i1],dp[1][x-2][i1]);
                    MaxSelf(suf_max,m+Sum(0,ind[x-2][i1]-1));
                    i1--;
                }
                MaxSelf(dp[1][x][i],suf_max);
            }

            i1=0;
            ll pref_max=-LINF;
            for(int i=0;i<sz(ind[x]);i++){
                while(i1<sz(ind[x-2]) && ind[x-2][i1]<=ind[x][i]){
                    ll m=max(dp[0][x-2][i1],dp[1][x-2][i1]);
                    MaxSelf(pref_max,m);
                    i1++;
                }
                MaxSelf(dp[1][x][i],pref_max+Sum(0,ind[x][i]-1));
            }

            i1=1;
            pref_max=-LINF;
            for(int i=0;i<sz(ind[x]);i++){
                if(i>0) pref_max+=Sum(ind[x][i-1],ind[x][i]-1);
                while(i1<sz(ind[x-1]) && ind[x-1][i1]<=ind[x][i]){
                    ll m=max(dp[0][x-1][i1],dp[1][x-1][i1]);
                    MaxSelf(pref_max,m+Sum(ind[x-1][i1],ind[x][i]-1));
                    i1++;
                }
                MaxSelf(dp[1][x][i],pref_max);
            }

            pref.clear(); pref[-1]=0;
            for(int i=0;i<sz(fish[x]);i++){
                int y=fish[x][i].fi;
                int w=fish[x][i].se;
                pref[y]=pref.upper_bound(y-1)->se+w;
            }

            i1=sz(ind[x-1])-1;
            suf_max=-LINF;
            for(int i=sz(ind[x])-1;i>=0;i--){
                if(i<sz(ind[x])-1) suf_max+=Sum(ind[x][i],ind[x][i+1]-1);
                while(i1>=0 && ind[x-1][i1]>ind[x][i]){
                    ll m=max(dp[0][x-1][i1],dp[1][x-1][i1]);
                    MaxSelf(suf_max,m+Sum(ind[x][i],ind[x-1][i1]-1));
                    i1--;
                }
                MaxSelf(dp[0][x][i],suf_max);
            }
        }
        else if(x==1){
            int i1=0;
            ll pref_max=-LINF;
            for(int i=0;i<sz(ind[x]);i++){
                if(i>0) pref_max+=Sum(ind[x][i-1],ind[x][i]-1);
                while(i1<sz(ind[x-1]) && ind[x-1][i1]<=ind[x][i]){
                    ll m=max(dp[0][x-1][i1],dp[1][x-1][i1]);
                    MaxSelf(pref_max,m+Sum(ind[x-1][i1],ind[x][i]-1));
                    i1++;
                }
                MaxSelf(dp[1][x][i],pref_max);
            }

            pref.clear(); pref[-1]=0;
            for(int i=0;i<sz(fish[x]);i++){
                int y=fish[x][i].fi;
                int w=fish[x][i].se;
                pref[y]=pref.upper_bound(y-1)->se+w;
            }

            i1=sz(ind[x-1])-1;
            ll suf_max=-LINF;
            for(int i=sz(ind[x])-1;i>=0;i--){
                if(i<sz(ind[x])-1) suf_max+=Sum(ind[x][i],ind[x][i+1]-1);
                while(i1>=0 && ind[x-1][i1]>ind[x][i]){
                    ll m=max(dp[0][x-1][i1],dp[1][x-1][i1]);
                    MaxSelf(suf_max,m+Sum(ind[x][i],ind[x-1][i1]-1));
                    i1--;
                }
                MaxSelf(dp[0][x][i],suf_max);
            }
        }
    }
    ll res=0;
    for(int i=0;i<sz(ind[N-1]);i++){
        ll m=max(dp[0][N-1][i],dp[1][N-1][i]);
        MaxSelf(res,m);
    }
    return res;
}

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