Submission #1224163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224163		Sharky	Catfish Farm (IOI22_fish)	C++17	81 / 100	1100 ms	154564 KiB

fish

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

using i32 = int32_t;
#define int long long

const int inf = 1e16;

vector<pair<int, int>> item[100002];
map<int, int> mp[2][100002];

long long max_weights(i32 N, i32 M, std::vector<i32> X, std::vector<i32> Y,
                      std::vector<i32> W) {
    for (int i = 0; i < M; i++) {
        X[i]++, Y[i]++;
        item[X[i]].push_back({Y[i], W[i]});
    }
    for (int i = 1; i <= N; i++) {
        sort(item[i].begin(), item[i].end());
        for (int j = 1; j < item[i].size(); j++) item[i][j].second += item[i][j - 1].second;
    }
    int ans = 0;
    mp[0][0][0] = 0;
    for (int i = 1; i <= N; i++) mp[0][0][i] = mp[1][0][i] = -inf;
    for (int i = 1; i <= N; i++) {
        vector<int> cand = {0, N};
        for (int j = 0; j < item[i-1].size(); j++) cand.push_back(item[i-1][j].first);
        for (int j = 0; j < item[i].size(); j++) cand.push_back(item[i][j].first - 1);
        auto que = [&] (int i, int j) {
            int mins = 0;
            if (!item[i].empty() && item[i].front().first <= j) {
                auto it = lower_bound(item[i].begin(), item[i].end(), make_pair(j+1, 0LL));
                --it;
                mins = (*it).second;
            }
            return mins;
        };
        vector<pair<int, int>> t0p, t1p;
        map<int, int> c0p = mp[0][i-1], c1p = mp[1][i-1];
        for (auto& [key, val] : mp[0][i-1]) {
            val += que(i, key);
            t0p.push_back({key, val});
        }
        for (auto& [key, val] : mp[1][i-1]) {
            val += que(i, key);
            t1p.push_back({key, val});
        }
        for (int j = (int) t0p.size() - 2; j >= 0; j--) {
            mp[0][i-1][t0p[j].first] = max(mp[0][i-1][t0p[j+1].first], t0p[j].second);
        }
        for (int j = (int) t1p.size() - 2; j >= 0; j--) {
            mp[1][i-1][t1p[j].first] = max(mp[1][i-1][t1p[j+1].first], t1p[j].second);
        }

        for (auto& j : cand) {
            int bruh = 0;
            auto it = mp[0][i-1].lower_bound(j);
            if (it != mp[0][i-1].end()) bruh = it->second;
            auto it2 = mp[1][i-1].lower_bound(j);
            if (it2 != mp[1][i-1].end()) bruh = max(bruh, it2->second);

            bruh -= que(i, j);

            mp[1][i][j] = bruh;
            ans = max(ans, bruh);
        }

        mp[0][i-1] = c0p;
        mp[1][i-1] = c1p;

        t0p.clear(), t1p.clear();

        for (auto& [key, val] : mp[0][i-1]) {
            val -= que(i-1, key);
            t0p.push_back({key, val});
        }

        for (int j = 1; j < t0p.size(); j++) {
            mp[0][i-1][t0p[j].first] = max(mp[0][i-1][t0p[j-1].first], t0p[j].second);
        }

        for (auto& j : cand) {
            int bruh = 0;
            if (!mp[0][i-1].empty() && mp[0][i-1].begin()->first <= j) {
                auto it = --mp[0][i-1].upper_bound(j);
                bruh = max(bruh, it->second);
            }
            if (i >= 2) {
                if (mp[1][i-2].count(0)) bruh = max(bruh, mp[1][i-2][0]);
            }
            bruh += que(i-1, j);
            mp[0][i][j] = bruh;
            ans = max(ans, bruh);
        }

        mp[0][i-1] = c0p;
        if (i >= 2) {
            vector<pair<int, int>> t2p;
            for (auto& [key, val] : mp[0][i-2]) {
                t2p.push_back({key, val});
            }
            for (int j = 1; j < t2p.size(); j++) {
                mp[0][i-2][t2p[j].first] = max(mp[0][i-2][t2p[j-1].first], t2p[j].second);
            }
            for (auto& j : cand) {
                int bruh = que(i-1, j);
                if (!mp[0][i-2].empty() && mp[0][i-2].begin()->first <= j) {
                    auto it = --mp[0][i-2].upper_bound(j);
                    bruh += it->second;
                }
                mp[0][i][j] = max(mp[0][i][j], bruh);
                ans = max(ans, bruh);
            }
        }
    }
    return ans;
}

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