제출 #1062348

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1062348		ProtonDecay314	메기 농장 (IOI22_fish)	C++17	100 / 100	252 ms	62900 KiB

fish

#include "fish.h"

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
typedef vector<vpi> vvpi;
typedef vector<vpll> vvpll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef short int si;
typedef vector<si> vsi;
typedef vector<vsi> vvsi;
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define L(varll, mn, mx) for(ll varll = (mn); varll < (mx); varll++)
#define LR(varll, mx, mn) for(ll varll = (mx); varll > (mn); varll--)
#define LI(vari, mn, mx) for(int vari = (mn); vari < (mx); vari++)
#define LIR(vari, mx, mn) for(int vari = (mx); vari > (mn); vari--)
#define INPV(varvec) for(auto& varveci : (varvec)) cin >> varveci
#define fi first
#define se second
#define pb push_back
#define INF(type) numeric_limits<type>::max()
#define NINF(type) numeric_limits<type>::min()
#define TCASES int t; cin >> t; while(t--)

struct fish {
    ll x, y, w;
};

ll max_weights(int N, int M, vi X, vi Y, vi W) {
    typedef vector<fish> vf;
    typedef vector<vf> vvf;

    vf f;

    L(i, 0ll, M) {
        f.pb({X[i], Y[i], W[i]});
    }

    sort(f.begin(), f.end(), [](const fish& f1, const fish& f2) {return f1.y < f2.y;});

    vvf fax;
    vvll dpinc;
    vvll dpdec;

    // vvll psum;

    L(i, 0ll, N) {
        vf faxr(1ll, {i, 0ll, 0ll});
        vll dpincr(1ll, 0ll);
        vll dpdecr(1ll, 0ll);
        // vll psumr(N + 1ll, 0ll);
        fax.pb(faxr);
        dpinc.pb(dpincr);
        dpdec.pb(dpdecr);
        // psum.pb(psumr);
    }

    L(i, 0ll, M) {
        assert(f[i].x < N);
        assert(f[i].y + 1ll <= N);
        fax[f[i].x].pb(f[i]);
        dpinc[f[i].x].pb(0ll);
        dpdec[f[i].x].pb(0ll);
        // cout << "Anya likes peanuts, Anya hates carrots" << endl;
        // psum[f[i].x][f[i].y + 1ll] += f[i].w; // += because we have multiple fish per cell
    }

    // Accumulating sums
    // L(i, 0ll, N) {
    //     L(j, 1ll, N + 1ll) {
    //         psum[i][j] += psum[i][j - 1ll];
    //     }
    // }


    // ! CAREFUL: you're adding another value
    L(i, 0ll, N) {
        fax[i].pb({i, N, 0ll});
        dpinc[i].pb(0ll);
        dpdec[i].pb(0ll);
    }

    ll ans = 0ll;

    L(i, 1ll, N) {
        // Increasing first
        const vf& fax1 = fax[i], fax2 = fax[i - 1ll], fax3 = fax[max(i - 2ll, 0ll)];

        ll f1s = fax1.size(), f2s = fax2.size(), f3s = fax3.size();

        // Case 1: dpinc, normal
        ll cur_pref_dpinc_max = dpinc[i - 1ll][0ll], f2i = 0ll;
        // ll f2_fish_sum = 0ll, f2fishi = 0ll;
        ll f2fishi = 0ll;
        
        // ! THIS LOOP IN PARTICULAR IS SCARY, MIGHT BE WRONG
        L(j, 0ll, f1s) {
            dpinc[i][j] = max(dpinc[i][j], cur_pref_dpinc_max);
            while(f2i < f2s && fax2[f2i].y <= fax1[j].y) {
                // Increase f2i: since j has increased, the possible values for f2i has also widened
                
                // First, increase the cur_pref_dpinc_max by the value of the current fish

                while(f2fishi < f2s && fax2[f2fishi].y < fax2[f2i].y) {
                    cur_pref_dpinc_max += (ll)fax2[f2fishi].w;
                    f2fishi ++;
                }

                cur_pref_dpinc_max = max(cur_pref_dpinc_max, dpinc[i - 1ll][f2i]); // A new fish is reachable. We need to check if picking just that fish is better

                // cout << fax2[f2i].y << " " << fax1[j].y << " " << (j + 1 < f1s ? fax1[j + 1].y : N) << "\n";
                // if(fax2[f2i].y == fax1[j].y && fax1[j].y < (j + 1 < f1s ? fax1[j + 1].y : N)) cur_pref_dpinc_max += (ll)fax2[f2i].w;

                f2i++;
            }
            while(f2fishi < f2s && fax2[f2fishi].y < fax1[j].y) {
                cur_pref_dpinc_max += (ll)fax2[f2fishi].w;
                f2fishi ++;
            }
            dpinc[i][j] = max(dpinc[i][j], cur_pref_dpinc_max);
        }

        // ! Developing here
        // Case 3: decreasing
        ll cur_suff_dpdec_max = max(dpinc[i - 1ll][f2s - 1ll], dpdec[i - 1ll][f2s - 1ll]);
        f2i = f2s - 1ll;

        LR(j, f1s - 1ll, -1ll) {
            cur_suff_dpdec_max += (ll)fax1[j].w; // Increment dpdec max with weight of current fish
            while(f2i >= 0 && fax2[f2i].y > fax1[j].y) {
                // ! Warning, might be wrong!
                // Idea: we only decrease when we get a new fish
                // Therefore, we only need to consider the current fish in the dpdec thing (or basta smth like that)
                cur_suff_dpdec_max = max(cur_suff_dpdec_max, max(dpinc[i - 1ll][f2i], dpdec[i - 1ll][f2i]) + (ll)fax1[j].w); // A new fish is reachable. We need to check if picking just that fish is better

                f2i--;
            }
            if(f2i >= 0 && fax2[f2i].y == fax1[j].y) { // ! Might be wrong!
                cur_suff_dpdec_max = max(cur_suff_dpdec_max, max(dpinc[i - 1ll][f2i], dpdec[i - 1ll][f2i])); 
                f2i--;
            }
            dpdec[i][j] = max(dpdec[i][j], cur_suff_dpdec_max);
        }

        if(i > 1ll) {
            // Case 2a: dpinc, transition, second to the last is less
            ll max_past_dp = 0ll;

            ll cur_dpinc2a_sum = 0ll;

            ll f3i = 0ll;
            ll f2i = 0ll;

            L(j, 0ll, f1s) {
                while(f3i < f3s && fax3[f3i].y <= fax1[j].y) {
                    // compare current max dp with current dp value
                    max_past_dp = max(max_past_dp, max(dpdec[i - 2ll][f3i], dpinc[i - 2ll][f3i]));
                    f3i++;
                }

                while(f2i < f2s && fax2[f2i].y < fax1[j].y) { // ! THIS MIGHT BITE YOU BACK LATER
                    cur_dpinc2a_sum += (ll)fax2[f2i].w;
                    f2i++;
                }

                dpinc[i][j] = max(dpinc[i][j], max_past_dp + cur_dpinc2a_sum);
                
                dpinc[i][j] = max(dpinc[i][j], dpdec[i - 1ll][0ll]); // Case 2b: dpinc, transition, second to the last is greater
            }
        }

        // Update answers
        L(j, 0ll, f1s) {
            ans = max(ans, dpdec[i][j]);
            ans = max(ans, dpinc[i][j]);
        }
    }

    // cout << "Y" << endl;

    // L(i, 0ll, N) {
    //     const vf& fax1 = fax[i];
    //     ll f1s = fax1.size();
    //     L(j, 0ll, f1s) {
    //         cout << fax1[j].y << " ";
    //     }
    //     cout << "\n";
    // }

    // cout << "DPINC" << endl;

    // L(i, 0ll, N) {
    //     const vf& fax1 = fax[i];
    //     ll f1s = fax1.size();
    //     L(j, 0ll, f1s) {
    //         cout << dpinc[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    // cout << "DPDEC" << endl;

    // L(i, 0ll, N) {
    //     const vf& fax1 = fax[i];
    //     ll f1s = fax1.size();
    //     L(j, 0ll, f1s) {
    //         cout << dpdec[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    // Final casework for the final answer (do this on the last column)
    // ll ans = 0ll;
    // const vf& lastcol = fax[N - 1ll];
    // ll lastcols = lastcol.size();

    // L(i, 0ll, lastcols) {
    //     ans = max(ans, max(dpdec[N - 1ll][i], dpinc[N - 1ll][i]));
    // }

    return ans;
}

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