제출 #755186

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

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

ll Sum(int x,int y1,int y2){
    if(pref[x].empty() || y1>y2) return 0;
    else{
        int r=(*(pref[x].lower_bound(y2))).se;
        int l=(*(pref[x].lower_bound(y1-1))).se;
        return r-l;
    }
}

ll MaxThree(int x,int p){
    return max({dp[0][x][p],dp[1][x][p],dp[2][x][p]});
}

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]))));
        Debug(x,inds[x]);
    }
    for(int x=0;x<N;x++){
        Debug(x);
        CalcPref(x);
        if(x==0){
            for(int p:inds[x]){
                dp[0][x][p]=dp[1][x][p]=dp[2][x][p]=0;
            }
        }
        else{
            int i1=sz(inds[x-1])-1,i2=sz(inds[x])-1;
            ll mx=0;
            while(i2>=0){
                int p1=inds[x-1][i1],p2=inds[x][i2];
                while(i1>=0 && p1>p2){
                    ll tmp=max(dp[1][x-1][p1],dp[2][x-1][p1])+Sum(x,p2,p1-1);
                    mx=max(mx,tmp);
                    i1--;
                }
                dp[2][x][p2]=mx;
                if(i2>0 && mx!=0){
                    int np2=inds[x][i2-1];
                    mx+=Sum(x,np2,p2-1);
                }
                i2--;
            }
            //Debug(1);
            mx=0;
            i1=0,i2=0;
            while(i2<sz(inds[x])){
                int p1=inds[x-1][i1],p2=inds[x][i2];
                while(i1<sz(inds[x-1]) && p1<p2){
                    ll tmp=max(dp[1][x-1][p1],dp[0][x-1][p1])+Sum(x,p1,p2-1);
                    mx=max(mx,tmp);
                    i1++;
                }
                dp[0][x][p2]=mx;
                if(i2<sz(inds[x])-1 && mx!=0){
                    int np2=inds[x][i2+1];
                    mx+=Sum(x,p2,np2-1);
                }
                i2++;
            }
            //Debug(2);
            for(int p:inds[x]){
                dp[1][x][p]=MaxThree(x-1,p);
            }
            if(x>1){
                i1=sz(inds[x-2])-1,i2=sz(inds[x])-1;
                mx=0;
                while(i2>=0){
                    int p1=inds[x-2][i1],p2=inds[x][i2];
                    while(i1>=0 && p1>=p2){
                        ll tmp=MaxThree(x-2,p1)+Sum(x-1,0,p1-1);
                        mx=max(mx,tmp);
                        i1--;
                    }
                    dp[0][x][p2]=max(dp[0][x][p2],mx);
                    i2--;
                }
                i1=0,i2=0;
                mx=0;
                while(i2<sz(inds[x])){
                    int p1=inds[x-2][i1],p2=inds[x][i2];
                    while(i1<sz(inds[x-2]) && p1<p2){
                        ll tmp=MaxThree(x-2,p1)+Sum(x-1,0,p2-1);
                        mx=max(mx,tmp);
                        i1++;
                    }
                    dp[0][x][p2]=max(dp[0][x][p2],mx);
                    i2++;
                }
                for(int p:inds[x]){
                    dp[2][x][p]=max(dp[2][x][p],MaxThree(x-1,N))+Sum(x,p,N-1);
                }
            }
        }
    }
    ll res=0;
    for(int p:inds[N-1]){
        res=max(res,MaxThree(N-1,p));
    }
    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