Submission #771382

#	Time	Username	Problem	Language	Result	Execution time	Memory
771382		PurpleCrayon	Catfish Farm (IOI22_fish)	C++17	37 / 100	1088 ms	29776 KiB

fish

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

#define sz(v) int(v.size())
#define ar array
typedef long long ll;
const int N = 1e5+10, MOD = 1e9+7;

vector<pair<int, int>> fish[N];
vector<int> use[N];

ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    for (int i = 0; i < m; i++) {
        fish[x[i]].emplace_back(y[i], w[i]);
        if (x[i]) use[x[i]-1].push_back(y[i]);
        if (x[i] < n-1) use[x[i]+1].push_back(y[i]);
    }

    for (int i = 0; i < n; i++) {
        use[i].push_back(-1);
        sort(use[i].begin(), use[i].end());
        sort(fish[i].begin(), fish[i].end());
    }

    vector<ll> prv_l{0}, prv_r{0};
    vector<int> prv_h{-1};
    vector<pair<int, int>> prv_fish;
    for (int c = 0; c < n; c++) {
        int k = sz(use[c]);

        vector<ll> cur_l(k), cur_r(k);
        auto cur_h = use[c];
        auto cur_fish = fish[c];

        vector<ll> ps_prv(sz(prv_fish));
        vector<ll> ps_cur(sz(cur_fish));
        for (int i = 0; i < sz(prv_fish); i++) {
            ps_prv[i] = prv_fish[i].second;
            if (i) ps_prv[i] += ps_prv[i-1];
        }

        for (int i = 0; i < sz(cur_fish); i++) {
            ps_cur[i] = cur_fish[i].second;
            if (i) ps_cur[i] += ps_cur[i-1];
        }

        ll mx_prv_l = *max_element(prv_l.begin(), prv_l.end());
        for (int j = 0; j < sz(cur_h); j++) {
            cur_r[j] = max(cur_r[j], mx_prv_l);

            ll my_ps_prv = upper_bound(prv_fish.begin(), prv_fish.end(), pair<int, int>{cur_h[j], MOD}) - prv_fish.begin() - 1;
            if (my_ps_prv < 0) my_ps_prv = 0;
            else my_ps_prv = ps_prv[my_ps_prv];

            for (int i = 0; i < sz(prv_h); i++) {
                ll cost_prv = prv_r[i];

                ll his_ps_prv = upper_bound(prv_fish.begin(), prv_fish.end(), pair<int, int>{prv_h[i], MOD}) - prv_fish.begin() - 1;
                if (his_ps_prv < 0) his_ps_prv = 0;
                else his_ps_prv = ps_prv[his_ps_prv];

                cost_prv += max(my_ps_prv - his_ps_prv, 0LL);
                /*
                for (auto f : prv_fish) if (prv_h[i] < f.first && f.first <= cur_h[j])
                    cost_prv += f.second;
                */

                cost_prv = max(cost_prv, prv_l[i]);
                cur_r[j] = max(cur_r[j], cost_prv);

                for (auto f : cur_fish) if (cur_h[j] < f.first && f.first <= prv_h[i])
                    cost_prv += f.second;


                cur_l[j] = max(cur_l[j], cost_prv);
            }
        }

        swap(prv_l, cur_l);
        swap(prv_r, cur_r);
        swap(prv_h, cur_h);
        swap(prv_fish, cur_fish);
    }

    ll ans = 0;
    for (ll x : prv_l) ans = max(ans, x);
    for (ll x : prv_r) ans = max(ans, x);
    return ans;
}

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