关于洛谷上评测IOI题

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

using namespace std;

typedef long long ll;

const int N = 1e5 + 10, M = 3e5 + 10;

int n, m, x[M], y[M], w[M];
ll f[M][2], g[M][2];
vector<int> c[N];

ll max_weights(int N1, int M1, vector<int> X, vector<int> Y, vector<int> W) {
    n = N1, m = M1;

    for (int i = 0; i < m; i++)
        x[i] = X[i], y[i] = Y[i], w[i] = W[i];

    y[m] = n, w[m] = 0;

    for (int i = 0; i < m; i++)
        c[x[i]].push_back(i);

    for (int i = 0; i < n; i++)
        c[i].push_back(m), sort(c[i].begin(), c[i].end(), [](int a, int b) {
        return y[a] > y[b];
    });

    for (int i = 1; i < n; i++) {
        int k = 0, it = 0;
        ll s = 0, sum = 0, mx1 = 0, mx0 = 0;

        for (int j = 0; j < c[i].size(); j++) {
            int t = c[i][j];
            sum += w[t];

            while (k < c[i - 1].size() && y[c[i - 1][k]] > y[t]) {
                while (it < c[i].size() && y[c[i][it]] >= y[c[i - 1][k]])
                    s -= w[c[i][it]], it++;

                mx1 = max(mx1, g[k][1] + s);
                mx0 = max(mx0, g[k][1]);
                k++;
            }

            f[j][1] = max(f[j][1], mx1 + sum);
            f[j][0] = max(f[j][0], mx0);
        }

        k = c[i - 1].size() - 1, mx0 = 0, mx1 = 0, s = 0, sum = 0;

        for (int j = c[i].size() - 1; j >= 0; j--) {
            int t = c[i][j];

            while (k >= 0 && y[c[i - 1][k]] < y[t]) {
                if (k + 1 < c[i - 1].size())
                    s -= w[c[i - 1][k + 1]];

                sum += w[c[i - 1][k]];
                mx0 = max(mx0, g[k][0] + s);
                mx1 = max(mx1, g[k][1]);
                k--;
            }

            f[j][0] = max({f[j][0], mx1, mx0 + sum});

            if (k >= 0 && y[c[i - 1][k]] == y[t])
                f[j][0] = max(f[j][0], g[k][1]);
        }

        f[0][1] = max(f[0][1], f[0][0]);

        for (int j = 0; j < c[i].size(); j++) {
            g[j][0] = f[j][0], g[j][1] = f[j][1];
            f[j][0] = f[j][1] = 0;
        }
    }


    ll ans = 0;

    for (int i = 0; i <= n; i++)
        ans = max(ans, g[i][1]);

    return ans;
}