Submission #1225745

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225745		the_coding_pooh	메기 농장 (IOI22_fish)	C++20	100 / 100	223 ms	48404 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
#define uwu return

using namespace std;

#define fs first
#define sc second

#define all(x) x.begin(), x.end()

const int SIZE = 1e5 + 5;

vector <int> valid_state[SIZE];

vector <pair<int, int>> fishes[SIZE];

vector <long long> dp[SIZE][2];

void chmax(long long &a, long long b){
    a = max(a, b);
    uwu;
}

void output(long long a, bool b){
    if(b)
        cerr << '\n';
    else
        cerr << a << ' ';
    return;
}

const long long INF = 1e18 + 7;

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    for (int i = 0; i < N; i++){
        valid_state[i].push_back(-1);
        valid_state[i].push_back(N - 1);
    }
    for (int i = 0; i < M; i++){
        if(X[i] != 0)
            valid_state[X[i] - 1].push_back(Y[i]);
        if(X[i] != N - 1)
            valid_state[X[i] + 1].push_back(Y[i]);
        fishes[X[i]].push_back({Y[i], W[i]});
    }
    for (int i = 0; i < N; i++){
        sort(all(valid_state[i]));
        sort(all(fishes[i]));
        for (auto j : valid_state[i]){
            dp[i][0].push_back(0);
            dp[i][1].push_back(0);
        }
    }
    for (int i = 1; i < N; i++){
        int nst_a = valid_state[i].size(), pst_a = valid_state[i - 1].size(), nfs_a = fishes[i].size(), pfs_a = fishes[i - 1].size();
        vector <long long> pp_pref, np_pref, pn_pref, nn_pref;
        // pp, np prefix of the previous fishes, pn, nn prefix of this round's fishes
        for (long long ptr = 0, sum = 0, j = 0; j < pst_a; j++){
            while(ptr < pfs_a && fishes[i - 1][ptr].fs <= valid_state[i - 1][j]){
                sum += fishes[i - 1][ptr].sc;
                ptr++;
            }
            pp_pref.push_back(sum);
        }
        for (long long ptr = 0, sum = 0, j = 0; j < nst_a; j++){
            while(ptr < pfs_a && fishes[i - 1][ptr].fs <= valid_state[i][j]){
                sum += fishes[i - 1][ptr].sc;
                ptr++;
            }
            np_pref.push_back(sum);
        }
        for (long long ptr = 0, sum = 0, j = 0; j < pst_a; j++){
            while(ptr < nfs_a && fishes[i][ptr].fs <= valid_state[i - 1][j]){
                sum += fishes[i][ptr].sc;
                ptr++;
            }
            pn_pref.push_back(sum);
        }
        for (long long ptr = 0, sum = 0, j = 0; j < nst_a; j++){
            while(ptr < nfs_a && fishes[i][ptr].fs <= valid_state[i][j]){
                sum += fishes[i][ptr].sc;
                ptr++;
            }
            nn_pref.push_back(sum);
        }

        for(auto j:dp[i - 1][1]){
            chmax(dp[i][0][0], j);
        }
        for (int j = 1; j < nst_a; j++){
            dp[i][0][j] = dp[i][0][0];
        }
        for (long long ptr = 0, mx = -INF, j = 0; j < nst_a; j++){
            while(ptr < pst_a && valid_state[i - 1][ptr] <= valid_state[i][j]){
                chmax(mx, dp[i - 1][0][ptr] - pp_pref[ptr]);
                ptr++;
            }
            chmax(dp[i][0][j], mx + np_pref[j]);
        }
        for (int j = 0; j < nst_a; j++){
            chmax(dp[i][1][j], dp[i][0][j]);
        }
        for (long long ptr = pst_a - 1, mx = -INF, j = nst_a - 1; j >= 0; j--){
            while(ptr >= 0 && valid_state[i - 1][ptr] >= valid_state[i][j]){
                chmax(mx, dp[i - 1][1][ptr] + pn_pref[ptr]);
                ptr--;
            }
            chmax(dp[i][1][j], mx - nn_pref[j]);
        }
    }

    // for (int i = 0; i < N; i++){
    //     for (int j = 0; j < (int)valid_state[i].size(); j++){
    //         output(i, 0);
    //         output(valid_state[i][j], 0);
    //         output(dp[i][0][j], 0);
    //         output(dp[i][1][j], 0);
    //         output(0, 1);
    //     }
    // }

    long long ans = 0;
    for(auto i:dp[N - 1][0]){
        chmax(ans, i);
    }
    for(auto i:dp[N - 1][1]){
        chmax(ans, i);
    }
    return ans;
}

• 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