Submission #1238802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238802		Zbyszek99	Catfish Farm (IOI22_fish)	C++20	9 / 100	153 ms	54008 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

vector<pll> dps[100003][2];
vector<pll> vals[100003];

ll max_weights(int n, int m, vi X, vi Y, vi W) 
{
    rep(i,m) X[i] += 2;
    rep(i,m)
    {
        vals[X[i]].pb({Y[i]+1,W[i]});
    }
    rep(i,n+2) sort(all(vals[i]));
    dps[0][0] = {{0,0}};
    dps[1][0] = {{0,0}};
    dps[0][1] = {{0,0}};
    dps[1][1] = {{0,0}};
    rep2(i,2,n+1)
    {
        vi dps_sort;
        forall(it,vals[i-1]) dps_sort.pb(it.ff);
        forall(it,vals[i+1]) dps_sort.pb(it.ff);
        sort(all(dps_sort));
        vi d = {0};
        vi right_add = {0};
        dps[i][0].pb({0,0});
        dps[i][1].pb({0,0});
        int pop = -1;
        forall(it,dps_sort)
        {
            if(it != pop) 
            {
                d.pb(it);
                right_add.pb(0);
                dps[i][0].pb({it,0});
                dps[i][1].pb({it,0});
            }
            pop = it;
        }
        // right add
        int cur_right = 0;
        ll right_sum = 0;
        rep(j,siz(d))
        {
            while(cur_right < siz(vals[i+1]) && vals[i+1][cur_right].ff <= d[j])
            {
                right_sum += vals[i+1][cur_right].ss;
                cur_right++;
            }
            right_add[j] = right_sum;
        }
        // smaller space
        ll max_dp = 0;
        forall(it,dps[i-2][0]) max_dp = max(max_dp,it.ss);
        forall(it,dps[i-2][1]) max_dp = max(max_dp,it.ss);
        rep(j,siz(d))
        {
            dps[i][0][j].ss = max_dp;
            dps[i][1][j].ss = max_dp;
        }
        // bigger space
        max_dp = 0;
        ll left_sum = 0;
        int cur_left_val = 0;
        int cur_left_dp = 0;
        rep(j,siz(d))
        {
            while(cur_left_dp < siz(dps[i-2][0]) && dps[i-2][0][cur_left_dp].ff <= d[j])
            {
                while(cur_left_val < siz(vals[i-1]) && vals[i-1][cur_left_val].ff <= dps[i-2][0][cur_left_dp].ff)
                {
                    left_sum += vals[i-1][cur_left_val].ss;
                    cur_left_val++;
                }
                max_dp = max(max_dp,dps[i-2][0][cur_left_dp].ss-left_sum);
                max_dp = max(max_dp,dps[i-2][1][cur_left_dp].ss-left_sum);
                cur_left_dp++;
            }
            while(cur_left_val < siz(vals[i-1]) && vals[i-1][cur_left_val].ff <= d[j])
            {
                left_sum += vals[i-1][cur_left_val].ss;
                cur_left_val++;
            }
            rep(d,2) dps[i][d][j].ss = max(dps[i][d][j].ss,max_dp + left_sum);
        }
        // smaller
        max_dp = 0;
        forall(it,dps[i-1][0]) max_dp = max(max_dp,it.ss);
        ll my_sum = 0;
        forall(it,vals[i]) my_sum += it.ss;
        int cur_my_vals = siz(vals[i])-1;
        for(int j = siz(d)-1; j >= 0; j--)
        {
            while(cur_my_vals >= 0 && vals[i][cur_my_vals].ff > d[j])
            {
                my_sum -= vals[i][cur_my_vals].ss;
                cur_my_vals--;
            }
            dps[i][0][j].ss = max(dps[i][0][j].ss,max_dp-my_sum);
        }
        // bigger
        max_dp = 0;
        left_sum = 0;
        my_sum = 0;
        cur_my_vals = 0;
        cur_left_val = 0;
        cur_left_dp = 0;
        rep(j,siz(d))
        {
            while(cur_left_dp < siz(dps[i-1][0]) && dps[i-1][0][cur_left_dp].ff <= d[j])
            {
                while(cur_my_vals < siz(vals[i]) && vals[i][cur_my_vals].ff <= dps[i-1][0][cur_left_dp].ff)
                {
                    my_sum += vals[i][cur_my_vals].ss;
                    cur_my_vals++;
                }
                while(cur_left_val < siz(vals[i-1]) && vals[i-1][cur_left_val].ff <= dps[i-1][0][cur_left_dp].ff)
                {
                    left_sum += vals[i-1][cur_left_val].ss;
                    cur_left_val++;
                }
                max_dp = max(max_dp,dps[i-1][1][cur_left_dp].ss-my_sum-left_sum);
                cur_left_dp++;
            }
            while(cur_my_vals < siz(vals[i]) && vals[i][cur_my_vals].ff <= dps[i-1][0][cur_left_dp].ff)
            {
                my_sum += vals[i][cur_my_vals].ss;
                cur_my_vals++;
            }
            while(cur_left_val < siz(vals[i-1]) && vals[i-1][cur_left_val].ff <= dps[i-1][0][cur_left_dp].ff)
            {
                left_sum += vals[i-1][cur_left_val].ss;
                cur_left_val++;
            }
            dps[i][1][j].ss = max(dps[i][1][j].ss,max_dp+left_sum);
        }
        dps[i][0][0].ss = 0;
        dps[i][1][0].ss = 0;
        forall(it,dps[i-1][0]) dps[i][0][0].ss = max(dps[i][0][0].ss,it.ss);
        forall(it,dps[i-1][1]) dps[i][0][0].ss = max(dps[i][0][0].ss,it.ss);
        forall(it,dps[i-2][0]) dps[i][1][0].ss = max(dps[i][1][0].ss,it.ss);
        forall(it,dps[i-2][1]) dps[i][1][0].ss = max(dps[i][1][0].ss,it.ss);
        rep(j,siz(d))
        {
            rep(d,2) dps[i][d][j].ss += right_add[j];
        }
    }
    ll ans = 0;
    forall(it,dps[n+1][0]) ans = max(ans,it.ss);
    forall(it,dps[n+1][1]) ans = max(ans,it.ss);
    return ans;
}

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