제출 #1055746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055746		vjudge1	메기 농장 (IOI22_fish)	C++17	58 / 100	1092 ms	102188 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<int>fishies[100010];
map<int,ll>fishiess[100010];
unordered_map<int,ll>dp[100010][2];
int N;
inline ll ones(int col,int len){
    return (--fishiess[col].upper_bound(len))->second;
}
struct segtree{
    unordered_map<int,ll>mp;
    void reset(){mp.clear();}
    ll query(int pos){
        ll ans=0;
        pos+=2;
        while(pos)
            ans=max(ans,mp[pos]),
            pos-=pos&-pos;
        return ans-(1ll<<50);
    }
    void upd(int p,ll x){
        p+=2;
        x+=1ll<<50;
        while(p<100100)
            mp[p]=max(mp[p],x),
            p+=p&-p;
    }
};
struct a_data_type{
    segtree Sec,First,Overal,Third;
    inline ll sec(int pos){
        return Sec.query(N-pos);
    }
    inline ll first(int pos){
        return First.query(pos);
    }
    inline ll overal(int pos){
        return Overal.query(N-pos);
    }
    inline ll third(int pos){
        return Third.query(pos);
    }
    void init(int i) {
        Overal.reset(),
        First.reset(),
        Sec.reset(),
        Third.reset();
        for(auto j:fishies[i]){
            j--;
            ll A=dp[i][0][j];
            ll B=dp[i][1][j];
            Overal.upd(N-j,max(A,B));
            First.upd(j,max(A,B)-ones(i+1,j));
            Sec.upd(N-j,A);
            Third.upd(j,B-ones(i,j)-ones(i+1,j));
        }
    }
} likehell[2];
ll max_weights(int N_,int M,vector<int> X,vector<int> Y,vector<int> W) {
    N=N_;
    for(int i=0;i<M;i++)
        fishies[X[i]+1].push_back(Y[i]+1),
        fishiess[X[i]+1][Y[i]+1]=W[i];
    for(int i=1;i<=N;i++){
        fishiess[i][N+1];
        fishiess[i][0];
        auto it=++fishiess[i].begin();
        while(it!=fishiess[i].end())
            it->second+=prev(it)->second,it++;
    }
    for(int i=1;i<=N;i++)
        fishies[i].push_back(1),
        fishies[i].push_back(N+1);
    fishiess[N+1][0];
    for(auto i:fishies[1])
        dp[1][1][i-1]=ones(2,i-1);
    int b=0;
    likehell[b].init(1);
    for(int i=2;i<=N;i++){
        for(auto rw:fishies[i]) {
            ll cons=ones(i+1,rw-1)+ones(i-1,rw-1);
            ll F=likehell[!b].first(rw-1);
            ll S=likehell[!b].overal(rw)-ones(i-1,rw-1);
            dp[i][1][rw-1]=cons+max(F,S);
        }
        for(auto rw2:fishies[i]){
            ll cons=ones(i+1,rw2-1)+ones(i-1,rw2-1);
            ll F=likehell[b].third(rw2-1);
            ll S=likehell[b].overal(rw2);
            dp[i][1][rw2-1]=max(dp[i][1][rw2-1],F+cons);
            dp[i][0][rw2-1]=S-ones(i,rw2-1)-ones(i-1,rw2-1)+cons;
        }
        for(auto rw2:fishies[i]) {
            ll K=likehell[b].sec(rw2-1)-ones(i,rw2-1);
            dp[i][0][rw2-1]=max(dp[i][0][rw2-1],ones(i+1,rw2-1)+K);
        }
        b=!b;
        likehell[b].init(i);
    }
    return likehell[b].overal(0);
}

• 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