Submission #746275

#	Time	Username	Problem	Language	Result	Execution time	Memory
746275		nguyentunglam	Catfish Farm (IOI22_fish)	C++17	0 / 100	59 ms	27984 KiB

fish

#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 3e5 + 10;
int order[N];
vector<int> fish[N], pref[N];
long long in[N], de[N], lastin[N], lastde[2][N];

long long calc(int h, int col) {
    if (h == -1 || col < 0 || fish[col].empty()) return 0;
    int idx = --upper_bound(fish[col].begin(), fish[col].end(), h) - fish[col].begin();
    return pref[col][idx];
}

long long max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {

    for(int i = 0; i < n; i++) fish[i].push_back(0), pref[i].push_back(0);

    for(int i = 0; i < m; i++) order[i] = i;
    sort(order, order + m, [&] (const int &A, const int &B) {
         return Y[A] < Y[B];
         });

    for(int cur = 0; cur < m; cur++) {
        int i = order[cur];
        fish[X[i]].push_back(Y[i]);
        pref[X[i]].push_back(pref[X[i]].back() + W[i]);
    }

    for(int i = 0; i < n; i++) fish[i].push_back(n + 1);

    de[0] = calc(n, 1);

    for(int i = 1; i < n; i++) {
        for(int &preh : fish[i]) {
            int h = preh - 1;
            in[i] = max(in[i], in[i - 1] + calc(h, i - 1) - calc(h, i));
            de[i] = max(de[i], de[i - 1] - calc(h, i) + calc(h, i + 1));
            lastde[1][i] = max(lastde[1][i], de[i - 1] - calc(h, i) + calc(h, i + 1));
            lastde[0][i] = max(lastde[0][i], de[i - 1] - calc(h, i));
            lastin[i] = max(lastin[i], in[i] + calc(n, i) - calc(h, i));

            if (i > 2) {
                int tmp = max(lastde[1][i - 2], lastde[0][i - 2] + calc(h, i - 1));
                in[i] = max(in[i], tmp - calc(h, i));
                de[i] = max(de[i], lastin[i - 2] + calc(n, i) - calc(h, i) + calc(h, i + 1));
            }
        }
    }
    cout << max(in[n - 1], de[n - 1]);

    return max(in[n - 1], de[n - 1]);
}

#ifdef ngu
int main() {

    freopen ("task.inp", "r", stdin);
    freopen ("task.out", "w", stdout);

    int n, m; cin >> n >> m;
    vector<int> x(m), y(m), w(m);
    for(int i = 0; i < m; i++) cin >> x[i] >> y[i] >> w[i];

    long long ret = max_weights(n, m, x, y, w);
}
#endif // ngu

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