Submission #1239349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239349		Hamed_Ghaffari	Catfish Farm (IOI22_fish)	C++20	100 / 100	133 ms	37984 KiB

fish

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

using ll = long long;

#define SZ(x) int(x.size())
#define maxs(a, b) (a = max(a, b))

const int MXN = 1e5+5;
const ll inf = 1e18;

vector<int> vec[MXN];
vector<ll> dp[3][MXN];

ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
    for(int i=0; i<m; i++) vec[++X[i]].push_back(i);
    Y.push_back(0);
    W.push_back(0);
    Y.push_back(n);
    W.push_back(0);
    for(int i=0; i<=n; i++) {
        vec[i].push_back(m);
        if(i) vec[i].push_back(m+1);
        sort(vec[i].begin(), vec[i].end(), [&](int x, int y) {
            return Y[x]<Y[y];
        });
        if(i) {
            dp[0][i].resize(SZ(vec[i-1]), i==1 ? 0 : -inf);
            for(int t : {1, 2})
                dp[t][i].resize(SZ(vec[i]), i==1 ? 0 : -inf);
        }
    }
    for(int i=2; i<=n; i++) {
        maxs(dp[0][i][0], *max_element(dp[0][i-1].begin(), dp[0][i-1].end())); // .. 0 0
        int ptr=0;
        ll sum=0;
        for(int j=0; j<SZ(vec[i-1]); j++) {
            while(ptr<SZ(vec[i]) && Y[vec[i][ptr]]<Y[vec[i-1][j]])
                sum += W[vec[i][ptr++]];
            maxs(dp[0][i][j], max(dp[1][i-1][j], dp[2][i-1][j])+sum);
        } // .. x 0

        ptr = SZ(vec[i-2])-1;
        ll mx = -inf;
        for(int j=SZ(vec[i])-1; j>=0; j--) {
            while(ptr>=0 && Y[vec[i-2][ptr]]>=Y[vec[i][j]])
                maxs(mx, dp[0][i-1][ptr--]);
            maxs(dp[1][i][j], mx);
            maxs(dp[2][i][j], mx);
        } // x 0 y (x>=y)

        ptr=0, sum=0, mx = -inf;
        int ptr2=0, ptr3=0;
        ll sum2 = 0;
        for(int j=0; j<SZ(vec[i]); j++) {
            while(ptr<SZ(vec[i-2]) && Y[vec[i-2][ptr]]<=Y[vec[i][j]]) {
                while(ptr2<SZ(vec[i-1]) && Y[vec[i-1][ptr2]]<Y[vec[i-2][ptr]])
                    sum2 += W[vec[i-1][ptr2++]];
                maxs(mx, dp[0][i-1][ptr++]-sum2);
            }
            while(ptr3<SZ(vec[i-1]) && Y[vec[i-1][ptr3]]<Y[vec[i][j]])
                sum += W[vec[i-1][ptr3++]];
            maxs(dp[1][i][j], mx+sum);
            maxs(dp[2][i][j], mx+sum);
        } // x 0 y (x<=y)

        ptr=0, sum=0;
        ptr2=0;
        mx = -inf, sum2=0;
        for(int j=0; j<SZ(vec[i]); j++) {
            while(ptr<SZ(vec[i-1]) && Y[vec[i-1][ptr]]<Y[vec[i][j]])
                sum += W[vec[i-1][ptr++]];
            while(ptr2<SZ(vec[i-1]) && Y[vec[i-1][ptr2]]<=Y[vec[i][j]]) {
                maxs(mx, dp[1][i-1][ptr2]-sum2);
                sum2 += W[vec[i-1][ptr2++]];
            }
            maxs(dp[1][i][j], mx+sum);
            maxs(dp[2][i][j], mx+sum);
        } // x y (x<=y)

        ptr=SZ(vec[i-1])-1;
        mx = -inf;
        sum = 0;
        ptr2=SZ(vec[i])-1;
        sum2=0;
        for(int j=SZ(vec[i])-1; j>=0; j--) {
            while(ptr>=0 && Y[vec[i-1][ptr]]>=Y[vec[i][j]]) {
                while(ptr2>=0 && Y[vec[i][ptr2]]>=Y[vec[i-1][ptr]])
                    sum2 += W[vec[i][ptr2--]];
                maxs(mx, dp[2][i-1][ptr--]-sum2);
            }
            sum += W[vec[i][j]];
            maxs(dp[2][i][j], mx+sum);
        } // x y (x>=y)
    }
    return max({
        *max_element(dp[0][n].begin(), dp[0][n].end()),
        *max_element(dp[1][n].begin(), dp[1][n].end()),
        *max_element(dp[2][n].begin(), dp[2][n].end())
    });
}

• 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