Submission #1072852

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072852		hotboy2703	Catfish Farm (IOI22_fish)	C++17	100 / 100	123 ms	39580 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MP make_pair
#define fi first
#define se second
#define pll pair <ll,ll>
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL<<(i)) 
ll n,m;
const ll MAXN = 1e5+100;
const ll INF = 1e18;
struct fish{
    ll y,w,v0,v1;
    bool operator < (const fish &p)const {
        return y < p.y;
    }
};
vector <fish> dp[MAXN];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    n=N,m=M;
    for (ll i = 0;i < m;i ++){
        dp[X[i]+1].push_back({Y[i],W[i],0,0});
    }
    for (ll i = 0;i <= n+1;i ++){
        dp[i].push_back({-1,0,0,0});
        sort(dp[i].begin(),dp[i].end());
        if (dp[i].back().y != n - 1)dp[i].push_back({n-1,0,0,0});
    }
    for (ll i = 2;i <= n;i ++){
        // cout<<"COL "<<i<<endl;
        dp[i-2][0].v1 = dp[i-1][0].v0;
        ll ptr = 0;
        ll max1 = -INF;
        ll sum = 0;
        for (auto &x:dp[i-1]){
            while (dp[i-2][ptr].y < x.y){
                max1 = max(max1,dp[i-2][ptr].v1 - sum);
                ptr++;
            }
            sum += x.w;
            x.v1 = max1 + sum;
            // cout<<"V1 "<<x.y<<' '<<x.v1<<'\n';
        }
        dp[i].back().v0 = dp[i-2].back().v1;
        sum = 0;
        for (auto &x:dp[i]){
            sum += x.w;
            x.v0 += sum;
        }
        ptr = sz(dp[i])-1;
        max1 = -INF;
        for (ll j = sz(dp[i+1])-2;j >= 0;j --){
            auto &x = dp[i+1][j];
            while (dp[i][ptr].y > x.y){
                sum -= dp[i][ptr].w;
                max1 = max(max1,dp[i][ptr].v0);
                ptr--;
            }
            x.v0 = max1 - sum;
            // cout<<"V0 "<<x.y<<' '<<x.v0<<'\n';
        }
        dp[i-1].back().v1 = max({dp[i-1].back().v1,dp[i-2].back().v1,dp[i][0].v0});
        // cout<<"V1 "<<dp[i-1].back().v1<<'\n';
    }
    return max(dp[n-1].back().v1,dp[n+1][0].v0);
}

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