Submission #1225457

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225457		hengliao	Catfish Farm (IOI22_fish)	C++20	81 / 100	1033 ms	454356 KiB

fish

#include "fish.h"
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>

typedef long long ll;

namespace{
    const ll mxN=3e6+5; // warning
    const ll inf=1e18;

    ll dp[mxN][2];
    ll dp2[mxN];
    ll mxdp2[mxN];
    ll a[mxN];
    vll pre[mxN];
    vll v[mxN];
    vll v2[mxN];
    vll v3[mxN];

    vector<pll> con;

    ll id(pll tar){
        return lower_bound(con.begin(), con.end(), tar)-con.begin();
    }

    bool check(pll tar){
        ll tep=id(tar);
        if(tep>=(ll) con.size()) return false;
        if(con[tep].F!=tar.F || con[tep].S!=tar.S){
            return false;
        }
        return true;
    }

    ll id2(ll tar, ll idx){
        return lower_bound(v[idx].begin(), v[idx].end(), tar)-v[idx].begin();
    }

    ll id3(ll tar, ll idx){
        return lower_bound(v2[idx].begin(), v2[idx].end(), tar)-v2[idx].begin();
    }

    ll id4(ll tar, ll idx){
        return lower_bound(v3[idx].begin(), v3[idx].end(), tar)-v3[idx].begin();
    }

    ll pre1(ll idx, ll tar){
        ll tep=upper_bound(v3[idx].begin(), v3[idx].end(), tar)-v3[idx].begin();
        tep--;
        if(tep<0) return 0LL;
        return pre[idx][tep];
    }

    ll f_big(ll idx, ll tar){
        ll tep=id2(tar, idx);
        return v[idx][tep];
    }

    ll f_small(ll idx, ll tar){
        ll tep=upper_bound(v2[idx].begin(), v2[idx].end(), tar)-v2[idx].begin();
        tep--;
        if(tep<0) return -1LL;
        return v2[idx][tep];
    }

    ll ans;
}

long long max_weights(int n, int m, vector<int> X, vector<int> Y,
                      vector<int> W) {
    memset(a, 0, sizeof(a));
    memset(dp, 0, sizeof(dp));
    memset(dp2, 0, sizeof(dp2));
    memset(mxdp2, 0, sizeof(mxdp2));
    for(ll i=0;i<m;i++){
        con.pb({X[i], Y[i]});
        con.pb({X[i], Y[i]-1});
        con.pb({X[i], Y[i]+1});
        v[X[i]].pb(Y[i]);
        v2[X[i]].pb(Y[i]+1);
        v3[X[i]].pb(Y[i]+1);
    }
    
    for(ll i=0;i<n;i++){
        v[i].pb(n);
        v2[i].pb(0);
        v3[i].pb(0);
        con.pb({i, n});
        con.pb({i, 0});
        sort(v[i].begin(), v[i].end());
        v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
        sort(v2[i].begin(), v2[i].end());
        v2[i].erase(unique(v2[i].begin(), v2[i].end()), v2[i].end());
        sort(v3[i].begin(), v3[i].end());
        v3[i].erase(unique(v3[i].begin(), v3[i].end()), v3[i].end());
    }
    sort(con.begin(), con.end());
    con.erase(unique(con.begin(), con.end()), con.end());
    for(ll i=0;i<m;i++){
        a[id({X[i], Y[i]})]=W[i];
    }
    for(ll i=0;i<n;i++){
        ll p=0;
        for(auto &it:v3[i]){
            ll cur=p;
            if(check({i, it-1})){
                cur+=a[id({i, it-1})];
            }
            pre[i].pb(cur);
            p=cur;
        }
    }
    ans=0;

    for(auto &it:v[0]){
        ll tep=f_small(1, it);
        dp2[id({1, tep})]=max(dp2[id({1, tep})], dp[id({0, it})][0]+pre1(1, tep));
        dp2[id({1, tep})]=max(dp2[id({1, tep})], dp[id({0, it})][1]+pre1(1, tep));
    }

    for(ll i=1;i<n;i++){
        for(ll k=0;k<2;k++){
            if(k==0){
                ll mx=-inf;
                ll pt=0;
                for(auto &it:v[i]){
                    while(pt<(ll) v[i-1].size() && v[i-1][pt]<=it){
                        mx=max(mx, dp[id({i-1, v[i-1][pt]})][0]-pre1(i-1, v[i-1][pt]));
                        pt++;
                    }
                    ll val=mx+pre1(i-1, it);
                    dp[id({i, it})][k]=max(dp[id({i, it})][k], val);
                }
                mx=-inf;
                pt=0;
                // ll pt2=0;
                for(auto &it:v[i]){
                    // mx=max(mx, dp2[i-1][j-1]-pre[i-1][j-1]);
                    while(pt<(ll) v2[i-1].size() && v2[i-1][pt]<=it-1){
                        mx=max(mx, dp2[id({i-1, v2[i-1][pt]})]-pre1(i-1, v2[i-1][pt]));
                        pt++;
                    }
                    ll val=mx+pre1(i-1, it);
                    dp[id({i, it})][k]=max(dp[id({i, it})][k], val);
                    dp[id({i, it})][k]=max(dp[id({i, it})][k], mxdp2[i-1]);
                }
            }
            else{
                ll mx=-inf;
                ll pt=(ll) v[i-1].size()-1;
                for(ll j=(ll) v[i].size()-1;j>=0;j--){
                    ll it=v[i][j];
                    while(pt>=0 && v[i-1][pt]>=it){
                        mx=max(mx, dp[id({i-1, v[i-1][pt]})][0]+pre1(i, v[i-1][pt]));
                        mx=max(mx, dp[id({i-1, v[i-1][pt]})][1]+pre1(i, v[i-1][pt]));
                        pt--;
                    }
                    dp[id({i, it})][k]=max(dp[id({i, it})][k], mx-pre1(i, it));
                }
            }
            for(auto &it:v[i]){
                ans=max(ans, dp[id({i, it})][k]);
            }
            if(i<n-1){
                for(auto &it:v[i]){
                    ll tep=f_small(i+1, it);
                    dp2[id({i+1, tep})]=max(dp2[id({i+1, tep})], dp[id({i, it})][0]+pre1(i+1, tep));
                    dp2[id({i+1, tep})]=max(dp2[id({i+1, tep})], dp[id({i, it})][1]+pre1(i+1, tep));
                }
            }
        }
        // for(ll t=0;t<=n;t++){
        dp2[id({i, 0})]=max(dp2[id({i, 0})], mxdp2[i-1]);
        // }
        for(auto &it:v2[i]){
            // dp2[id({i, it})]=max(dp2[id({i, it})], dp[id({i-1, f_big(i-1, it)})][0]+pre1(i, it));
            // dp2[id({i, it})]=max(dp2[id({i, it})], dp[id({i-1, f_big(i-1, it)})][1]+pre1(i, it));
            mxdp2[i]=max(mxdp2[i], dp2[id({i, it})]);
            ans=max(ans, dp2[id({i, it})]);
        }
    }
    return ans;
}   

• Subtask 1: 0 / 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: 0 / 16