제출 #757100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757100		Urvuk3	메기 농장 (IOI22_fish)	C++17	58 / 100	1097 ms	272092 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); }

const int mxM=3e5+1;
const int mxN=1e5+1;

vector<int> inds[mxN];
map<int,ll> dp[3][mxN],val[mxN];
//map<int,ll,greater<int>> pref[mxN];
deque<pair<int,ll>> pref[mxN];

void CalcPref(int x){
    for(auto p:val[x]){
        int y=p.fi;
        ll w=p.se;
        ll ps=w+(!pref[x].empty() ? (*pref[x].begin()).se : 0LL);
        pref[x].push_front({y,ps});
        //pref[x][y]=w+(!pref[x].empty() ? (*pref[x].begin()).se : 0LL);
    }
}

ll Sum(int x,int y1,int y2){
    if(y1>y2) return 0;
    else{
        auto lb2=lower_bound(all(pref[x]),make_pair(y2,LINF),greater<pair<int,ll>>());
        auto lb1=lower_bound(all(pref[x]),make_pair(y1-1,LINF),greater<pair<int,ll>>());
        auto e=pref[x].end();
        ll r=(lb2!=e ? (*lb2).se : 0);
        ll l=(lb1!=e ? (*lb1).se : 0);
        return r-l;
    }
}

ll MaxDP(int x,int p,vector<int> v){
    if(!dp[0][x].count(p)) return 0;
    ll ret=-LINF;
    for(int d:v) ret=max(ret,dp[d][x][p]);
    return ret;
}

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){
    for(int i=0;i<M;i++){
        val[X[i]][Y[i]]=W[i];
        if(X[i]-1>=0) inds[X[i]-1].pb(Y[i]+1);
        if(X[i]+1<N) inds[X[i]+1].pb(Y[i]+1);
    }
    for(int x=0;x<N;x++){
        inds[x].pb(0); inds[x].pb(N);
        sort(all(inds[x]));
        inds[x].resize(distance(inds[x].begin(),unique(all(inds[x]))));
    }
    for(int x=0;x<N;x++){
        CalcPref(x);
        if(x==0){
            for(int p:inds[x]){
                for(int d=0;d<3;d++){
                    dp[d][x][p]=0;
                }
            }
        }
        else{
            //0:Trazimo dp gde je pile na x-1 manji nego pile na x
            int i1=0,i2=0;
            int p1=0,p2=0;
            ll mx=-LINF;
            while(i2<sz(inds[x])){
                while(i1<sz(inds[x-1]) && p1<p2){
                    ll tmp=MaxDP(x-1,p1,{1,0})+Sum(x-1,p1,p2-1);
                    MaxSelf(mx,tmp);
                    i1++;
                    if(i1<sz(inds[x-1])) p1=inds[x-1][i1];
                }
                MaxSelf(dp[0][x][p2],mx);
                if(i2<sz(inds[x])-1){
                    int np2=inds[x][i2+1];
                    mx+=Sum(x-1,p2,np2-1);
                }
                i2++;
                if(i2<sz(inds[x])) p2=inds[x][i2];
            }

            //1:Trazimo dp gde je pile na x-1 jednak sa pile na x
            for(int p:inds[x]){
                MaxSelf(dp[1][x][p],MaxDP(x-1,p,{0,1,2}));
            }

            //2:Trazimo dp gde je pile na x-1 veci nego pile na x
            i1=sz(inds[x-1])-1,i2=sz(inds[x])-1;
            p1=N,p2=N;
            mx=-LINF;
            while(i2>=0){
                while(i1>=0 && p1>p2){
                    ll tmp=MaxDP(x-1,p1,{1,2})+Sum(x,p2,p1-1);
                    MaxSelf(mx,tmp);
                    i1--;
                    if(i1>=0) p1=inds[x-1][i1];
                }
                MaxSelf(dp[2][x][p2],mx);
                if(i2>0 && mx!=0){
                    int np2=inds[x][i2-1];
                    mx+=Sum(x,np2,p2-1);
                }
                i2--;
                if(i2>=0) p2=inds[x][i2];
            }

            if(x>1){
                //Trazimo dp gde je pile na x-1 jednak 0 i na x-1 je dolina
                i1=sz(inds[x-2])-1,i2=sz(inds[x])-1;
                p1=N,p2=N;
                mx=-LINF;
                while(i2>=0){
                    while(i1>=0 && p1>=p2){
                        ll tmp=MaxDP(x-2,p1,{0,1,2})+Sum(x-1,0,p1-1);
                        MaxSelf(mx,tmp);
                        i1--;
                        if(i1>=0) p1=inds[x-2][i1];
                    }
                    MaxSelf(dp[0][x][p2],mx);
                    i2--;
                    if(i2>=0) p2=inds[x][i2];
                }
                i1=0,i2=0;
                p1=0,p2=0;
                mx=-LINF;
                while(i2<sz(inds[x])){
                    while(i1<sz(inds[x-2]) && p1<p2){
                        ll tmp=MaxDP(x-2,p1,{0,1,2})+Sum(x-1,0,p2-1);
                        MaxSelf(mx,tmp);
                        i1++;
                        if(i1<sz(inds[x-2])) p1=inds[x-2][i1];
                    }
                    MaxSelf(dp[0][x][p2],mx);
                    i2++;
                    if(i2<sz(inds[x])) p2=inds[x][i2];
                }

                //Trazimo dp gde je pile na x-1 jednak N i na x-1 je vrh
                for(int p:inds[x]){
                    MaxSelf(dp[2][x][p],dp[0][x-1][N]+Sum(x,p,N-1));
                }
            }
        }
    }
    /*
    for(int x=0;x<N;x++){
        Debug(x); cerr<<":"<<endl;
        for(int d=0;d<3;d++){
            for(int p:inds[x]){
                Debug(d,x,p,dp[d][x][p]);
            }
        }
        cerr<<endl<<"------------------------"<<endl;
    }
    */
    ll res=0;
    for(int p:inds[N-1]){
        MaxSelf(res,MaxDP(N-1,p,{0,1,2}));
    }
    return res;
}

/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/

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