Submission #800740

#	Time	Username	Problem	Language	Result	Execution time	Memory
800740		QwertyPi	Catfish Farm (IOI22_fish)	C++17	23 / 100	361 ms	96980 KiB

fish

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

using namespace std;

const long long INF = (1LL << 60);
struct value{
    int y; long long ans;
};

struct catfish{
    int y, w; long long s;
    bool operator< (const catfish& o) const {
        return y < o.y;
    }
};

const int MAXN = 1e5 + 11;
vector<value> DP[3][MAXN];
vector<catfish> F[MAXN];
int S[MAXN];

long long prefix_weight(int x, int y){
    int idx = upper_bound(F[x].begin(), F[x].end(), catfish{y}) - F[x].begin() - 1;
    return F[x][idx].s;
}

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    for(int i = 0; i < M; i++) X[i]++;
    for(int i = 0; i <= N + 1; i++){
        F[i].push_back({-1, 0});
    }
    for(int i = 0; i < M; i++){
        F[X[i]].push_back({Y[i], W[i]});
    }
    for(int i = 1; i <= N; i++){
        sort(F[i].begin(), F[i].end());
        for(int j = 1; j < (int) F[i].size(); j++){
            F[i][j].s = F[i][j - 1].s + F[i][j].w;
        }
    }
    for(int i = 1; i <= N; i++){
        vector<int> sp {-1};
        for(auto [y, w, s] : F[i - 1]) sp.push_back(y);
        for(auto [y, w, s] : F[i]) sp.push_back(y);
        for(auto [y, w, s] : F[i + 1]) sp.push_back(y);
        sort(sp.begin(), sp.end()); sp.resize(unique(sp.begin(), sp.end()) - sp.begin());
        for(auto v : sp) DP[0][i].push_back({v, 0}), DP[1][i].push_back({v, 0}), DP[2][i].push_back({v, 0}); S[i] = sp.size();
    }

    for(int x = 1; x <= N; x++){
        int pd0 = 0, pd1 = 0, pd2 = 0;
        
        // 0 to 0
        pd0 = 0; long long dp_max = 0;
        for(auto& [h, ans] : DP[0][x]){
            while(pd0 < S[x - 1] && DP[0][x - 1][pd0].y <= h) dp_max = max(dp_max, DP[0][x - 1][pd0].ans - prefix_weight(x - 1, DP[0][x - 1][pd0].y) - prefix_weight(x, DP[0][x - 1][pd0].y)), pd0++;
            ans = max(ans, prefix_weight(x - 1, h) + prefix_weight(x + 1, h) + dp_max);
        }

        // 2 to 0
        pd2 = S[x - 1] - 1; dp_max = -INF;
        for(int i = S[x] - 1; i >= 0; i--){
            int h = DP[0][x][i].y;
            while(pd2 >= 0 && DP[2][x - 1][pd2].y >= h) dp_max = max(dp_max, DP[2][x - 1][pd2--].ans);
            DP[0][x][i].ans = max(DP[0][x][i].ans, prefix_weight(x + 1, h) + dp_max);
        }

        // 2 to 0
        pd2 = 0; dp_max = -INF;
        for(auto& [h, ans] : DP[0][x]){
            while(pd2 < S[x - 1] && DP[2][x - 1][pd2].y <= h) dp_max = max(dp_max, DP[2][x - 1][pd2].ans - prefix_weight(x - 1, h)), pd2++;
            ans = max(ans, prefix_weight(x - 1, h) + prefix_weight(x + 1, h) + dp_max);
        }

        // 0 and 1 to 1
        pd0 = S[x - 1] - 1, pd1 = S[x - 1] - 1; dp_max = -INF;
        for(int i = S[x] - 1; i >= 0; i--){
            int h = DP[1][x][i].y;
            while(pd0 >= 0 && DP[0][x - 1][pd0].y >= h) dp_max = max(dp_max, DP[0][x - 1][pd0--].ans);
            while(pd1 >= 0 && DP[1][x - 1][pd1].y >= h) dp_max = max(dp_max, DP[1][x - 1][pd1--].ans);
            DP[1][x][i].ans = max(DP[1][x][i].ans, dp_max + prefix_weight(x + 1, h) - prefix_weight(x, h));
        }

        // 0 and 1 to 2
        pd0 = S[x - 1] - 1, pd1 = S[x - 1] - 1;
        for(int i = S[x] - 1; i >= 0; i--){
            int h = DP[2][x][i].y; dp_max = 0;
            while(pd0 >= 0 && DP[0][x - 1][pd0].y >= h) dp_max = max(dp_max, DP[0][x - 1][pd0].ans), pd0--;
            while(pd1 >= 0 && DP[1][x - 1][pd1].y >= h) dp_max = max(dp_max, DP[1][x - 1][pd1].ans), pd1--;
            DP[2][x][i].ans = max(DP[2][x][i].ans, dp_max);
        }

        // 2 to 2
        dp_max = 0;
        for(int i = 0; i < S[x - 1]; i++){
            dp_max = max(dp_max, DP[2][x - 1][i].ans);
        }
        DP[2][x][0].ans = dp_max;
    }

    long long ans = 0;
    for(int i = 0; i < 3; i++){
        for(int j = 0; j < S[N]; j++){
            ans = max(ans, DP[i][N][j].ans);
        }
    }
    return ans;
    /*
    cout << "INC" << endl;
    for(int x = 1; x <= N; x++){
        for(auto [y, ans] : DP[0][x]){
            cout << "[" << y << ' ' << ans << "]" << ' ';
        }
        cout << endl;
    }

    cout << "DEC" << endl;
    for(int x = 1; x <= N; x++){
        for(auto [y, ans] : DP[1][x]){
            cout << "[" << y << ' ' << ans << "]" << ' ';
        }
        cout << endl;
    }

    cout << "ZERO" << endl;
    for(int x = 1; x <= N; x++){
        for(auto [y, ans] : DP[2][x]){
            cout << "[" << y << ' ' << ans << "]" << ' ';
        }
        cout << endl;
    }
    */
}

Compilation message (stderr)

fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:48:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   48 |         for(auto v : sp) DP[0][i].push_back({v, 0}), DP[1][i].push_back({v, 0}), DP[2][i].push_back({v, 0}); S[i] = sp.size();
      |         ^~~
fish.cpp:48:110: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   48 |         for(auto v : sp) DP[0][i].push_back({v, 0}), DP[1][i].push_back({v, 0}), DP[2][i].push_back({v, 0}); S[i] = sp.size();
      |                                                                                                              ^

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