Submission #838102

#	Time	Username	Problem	Language	Result	Execution time	Memory
838102		erekle	Catfish Farm (IOI22_fish)	C++17	100 / 100	256 ms	87300 KiB

fish

#include "fish.h"
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

struct Catfish{
    int x, y, w;
    Catfish() {}
    Catfish(int X, int Y, int W): x(X), y(Y), w(W) {}
    bool operator < (const Catfish &c2) {
        return pair<int, int>{x, y} < pair<int, int>{c2.x, c2.y};
    }
    string str() {
        return "(" + to_string(x) + "," + to_string(y) + "," + to_string(w) + ")";
    }
};

const long long INF = 1e18;

bool testing = false;

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
    vector<vector<Catfish>> inCol(1+N);
    for (int i = 0; i < M; ++i) {
        ++X[i], ++Y[i];
        inCol[X[i]].emplace_back(X[i], Y[i], W[i]);
    }
    // for (int i = 1; i <= N; ++i) {
    //     for (int j = 1; j <= N; ++j) {
    //         bool found = false;
    //         for (Catfish &c : inCol[i]) {
    //             if (c.y == j) found = true;
    //             break;
    //         }
    //         if (!found) inCol[i].emplace_back(i, j, 0);
    //     }
    // }
    for (int i = 0; i <= N; ++i) inCol[i].emplace_back(i, 0, 0), sort(inCol[i].begin(), inCol[i].end());

if (testing) {
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j < (int)inCol[i].size(); ++j) cout << inCol[i][j].str() << ' ';
        cout << endl;
    }
}

    vector<vector<long long>> sumBelow(1+N);
    for (int i = 0; i <= N; ++i) {
        sumBelow[i].resize(inCol[i].size());
        for (size_t j = 0; j < sumBelow[i].size(); ++j) {
            sumBelow[i][j] = (j == 0 ? 0 : sumBelow[i][j-1]) + inCol[i][j].w;
        }
    }

if (testing) {
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j < (int)sumBelow[i].size(); ++j) cout << sumBelow[i][j] << ' ';
        cout << endl;
    }
}

    vector<vector<int>> heights(1+N);
    for (int i = 1; i <= N; ++i) {
        if (i) {
            for (const Catfish &c : inCol[i-1]) heights[i].push_back(c.y);
        }
        if (i<N) {
            for (const Catfish &c : inCol[i+1]) heights[i].push_back(c.y);
        }
        sort(heights[i].begin(), heights[i].end());
        heights[i].resize(unique(heights[i].begin(), heights[i].end()) - heights[i].begin());        
    }
    heights[0].push_back(0);

if (testing) {
    cout << "HEIGHTS:" << endl;
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j < (int)heights[i].size(); ++j) cout << heights[i][j] << ' ';
        cout << endl;
    }
}
    
    vector<vector<long long>> inside(1+N), insideLeft(1+N), insideRight(1+N);
    for (int i = 0; i <= N; ++i) {
        inside[i] = insideLeft[i] = insideRight[i] = vector<long long>(heights[i].size());
        size_t nxt = 0, nxtLeft = 0, nxtRight = 0;
        long long sum = 0, sumLeft = 0, sumRight = 0;
        for (size_t j = 0; j < heights[i].size(); ++j) {
            int h = heights[i][j];
            while (nxt < inCol[i].size() && inCol[i][nxt].y <= h) sum += inCol[i][nxt++].w;
            if (i) {
                while (nxtLeft < inCol[i-1].size() && inCol[i-1][nxtLeft].y <= h) sumLeft += inCol[i-1][nxtLeft++].w;
            }
            if (i<N) {
                while (nxtRight < inCol[i+1].size() && inCol[i+1][nxtRight].y <= h) sumRight += inCol[i+1][nxtRight++].w;
            }
            inside[i][j] = sum, insideLeft[i][j] = sumLeft, insideRight[i][j] = sumRight;
        }
    }

if (testing) {
    cout << "INSIDE:" << endl;
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j < (int)inside[i].size(); ++j) cout << inside[i][j] << ' ';
        cout << endl;
    }
    cout << " left:" << endl;
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j < (int)insideLeft[i].size(); ++j) cout << insideLeft[i][j] << ' ';
        cout << endl;
    }
    cout << " right:" << endl;
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j < (int)insideRight[i].size(); ++j) cout << insideRight[i][j] << ' ';
        cout << endl;
    }
}

    vector<vector<long long>> dp[2]; // 0 means >= previous, 1 means <= previous
    dp[0] = dp[1] = vector<vector<long long>>(1+N);

    /*
    observation: exists solution in which all local minimums have height 0
     and all local maximums have height effectively equal to N
    */

if (testing)    cout << endl << "DP\n";
    long long ans = 0;
    dp[0][0] = dp[1][0] = {0};
    for (int x = 1; x <= N; ++x) {
        dp[0][x] = dp[1][x] = vector<long long>(heights[x].size());
        { // increasing
            long long maxDif = -INF; // max score - inside
            size_t nxtLeft = 0;
            for (size_t j = 0; j < heights[x].size(); ++j) {
                int y = heights[x][j];
                while (nxtLeft < heights[x-1].size() && heights[x-1][nxtLeft] <= y) {
                    maxDif = max(maxDif, dp[0][x-1][nxtLeft] - inside[x-1][nxtLeft]);
                    ++nxtLeft;
                }
if (testing)                cout << " for " << x << " " << j << " have dif " << maxDif << " giving " << insideLeft[x][j] + maxDif << endl;
                dp[0][x][j] = max(dp[0][x][j], insideLeft[x][j] + maxDif);
            }
        }
        { // decreasing
            long long maxSum = -INF; // max score + inside right
            int nxtLeft = (int)heights[x-1].size()-1;
            for (int j = (int)heights[x].size()-1; j >= 0; --j) {
                int y = heights[x][j];
                while (nxtLeft >= 0 && heights[x-1][nxtLeft] >= y) {
                    maxSum = max(maxSum, dp[1][x-1][nxtLeft] + insideRight[x-1][nxtLeft]);
                    --nxtLeft;
                }
if (testing)                cout << " for " << x << " " << j << " have sum " << maxSum << " giving " << maxSum - inside[x][j] << endl;
                dp[1][x][j] = max(dp[1][x][j], maxSum - inside[x][j]);
            }
        }
        { // after local maximum
            size_t j1 = heights[x-1].size()-1;
            int h1 = heights[x-1][j1];
            for (size_t j = 0; j < heights[x].size() && heights[x][j] <= h1; ++j) {
                long long score = max(dp[0][x-1][j1], dp[1][x-1][j1]);
                score += insideRight[x-1][j1] - inside[x][j];
                dp[1][x][j] = max(dp[1][x][j], score);
                if (heights[x][j] == h1) dp[0][x][j] = max(dp[0][x][j], score);
            }
        }
        if (x > 1) { // after local minimum
            // case: column before 0 is higher than column after
            long long maxSum = 0;
            for (size_t j = 0; j < heights[x-2].size(); ++j) {
                maxSum = max(maxSum, max(dp[0][x-2][j], dp[1][x-2][j]) + insideRight[x-2][j]);
            }
            for (size_t j = 0; j < heights[x].size(); ++j) {
                dp[0][x][j] = max(dp[0][x][j], maxSum);
                if (!j) dp[1][x][j] = max(dp[1][x][j], maxSum);
            }

            // case: column after 0 is higher than column before
            long long maxScore = 0;
            for (size_t j = 0; j < heights[x-2].size(); ++j) {
                maxScore = max(maxScore, max(dp[0][x-2][j], dp[1][x-2][j]));
            }
            for (size_t j = 0; j < heights[x].size(); ++j) {
                dp[0][x][j] = max(dp[0][x][j], maxScore + insideLeft[x][j]);
                if (!j) dp[1][x][j] = max(dp[1][x][j], maxScore + insideLeft[x][j]);
            }
        }

        for (size_t j = 0; j < heights[x].size(); ++j) {
            ans = max(ans, max(dp[0][x][j], dp[1][x][j]));
        }
    }
    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