Submission #742312

#	Time	Username	Problem	Language	Result	Execution time	Memory
742312		MilosMilutinovic	Catfish Farm (IOI22_fish)	C++17	0 / 100	124 ms	111560 KiB

fish

/* todo: debug */
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
int sz[N];
vector<int> v[N];
vector<pair<int, int>> my[N];
vector<ll> dpinc[N];
vector<ll> dpdec[N];
vector<ll> pref[N];
long long max_weights(int n, int m, std::vector<int> x, std::vector<int> y,
                      std::vector<int> w) {
    for (int i = 1; i <= n; i++)
        v[i].push_back(0);
    for (int i = 0; i < m; i++) {
        x[i]++; y[i]++;
        v[x[i] - 1].push_back(y[i]);
        v[x[i] + 1].push_back(y[i]);
        v[x[i]].push_back(y[i]);
        my[x[i]].emplace_back(y[i], w[i]);
    }
    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(), v[i].end());
        v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
        sz[i] = (int) v[i].size();
        dpinc[i].resize(sz[i]);
        dpdec[i].resize(sz[i]);
        pref[i].resize(sz[i]);
        for (auto& p : my[i]) {
            int idx = (int) (lower_bound(v[i].begin(), v[i].end(), p.first) - v[i].begin());
            pref[i][idx] += p.second;
        }
        for (int j = 1; j < sz[i]; j++) pref[i][j] += pref[i][j - 1];
    }
    {
        // build dpdec 1
        int ptr = 0;
        ll s = 0;
        for (int j = 0; j < sz[1]; j++) {
            while (ptr < sz[2] && v[2][ptr] <= v[1][j]) {
                s = pref[2][ptr];
                ptr++;
            }
            dpdec[1][j] = s;
        }
    }
    for (int i = 2; i <= n; i++) {
        {
            // inc -> inc
            ll mx = 0;
            ll s = 0;
            int ptr = 0;
            for (int j = 0; j < sz[i]; j++) {
                while (ptr < sz[i - 1] && v[i - 1][ptr] <= v[i][j]) {
                    s = pref[i - 1][ptr];
                    mx = max(mx, dpinc[i - 1][ptr] - pref[i - 1][ptr]);
                    ptr++;
                }
                dpinc[i][j] = mx + s;
            }
        }
        {
            // dec -> dec
            ll mx = 0;
            int ptr = sz[i - 1];
            for (int j = sz[i] - 1; j >= 0; j--) {
                while (ptr >= 0 && v[i - 1][ptr] >= v[i][j]) {
                    mx = max(mx, dpdec[i - 1][ptr]);
                    ptr++;
                }
                dpdec[i][j] = mx - pref[i][j];
            }
        }
        {
            // my inc -> my dec
            for (int j = 0; j < sz[i]; j++) dpdec[i][j] = max(dpdec[i][j], dpinc[i][j]);
        }
        {
            // add right to dpdec
            int ptr = 0;
            ll s = 0;
            for (int j = 0; j < sz[i]; j++) {
                while (ptr < sz[i + 1] && v[i + 1][ptr] <= v[i][j]) {
                    s = pref[i + 1][ptr];
                    ptr++;
                }
                dpdec[i][j] += s;
            }
        }
        if (i > 2) {
            // connect with i - 2
            {
                // i - 2 is greater
                ll mx = 0;
                for (int j = 0; j < sz[i - 2]; j++) mx = max(mx, dpdec[i - 2][j]);
                int ptr = 0;
                ll s = 0;
                for (int j = 0; j < sz[i]; j++) {
                    while (ptr < sz[i - 1] && v[i - 1][ptr] <= v[i][j]) {
                        s = pref[i - 1][ptr];
                        ptr++;
                    }
                    dpdec[i][j] = max(dpdec[i][j], mx - s);
                }
            }
            {
                ll mx = 0;
                int ptr = 0;
                ll s = 0;
                for (int j = 0; j < sz[i - 2]; j++) {
                    while (ptr < sz[i - 1] && v[i - 1][ptr] <= v[i - 2][j]) {
                        s = pref[i - 1][ptr];
                        ptr++;
                    }
                    mx = max(mx, dpdec[i - 2][j] - s);
                }
                ptr = 0;
                s = 0;
                for (int j = 0; j < sz[i]; j++) {
                    while (ptr < sz[i - 1] && v[i - 1][ptr] <= v[i][j]) {
                        s = pref[i - 1][ptr];
                        ptr++;
                    }
                    dpdec[i][j] = max(dpdec[i][j], mx + s);
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < sz[i]; j++)
            ans = max(ans, dpdec[i][j]);
    return ans;
}
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/

• 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