oj.uz

Submission #1062348

# Submission time Handle Problem Language Result Execution time Memory
1062348 2024-08-17T03:42:37 Z ProtonDecay314 Catfish Farm (IOI22_fish) C++17
100 / 100
 252 ms 62900 KB 
#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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 36504 KB Output is correct
2 Correct 63 ms 38596 KB Output is correct
3 Correct 35 ms 23148 KB Output is correct
4 Correct 35 ms 23652 KB Output is correct
5 Correct 127 ms 62900 KB Output is correct
6 Correct 252 ms 61100 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 81 ms 45932 KB Output is correct
3 Correct 95 ms 53436 KB Output is correct
4 Correct 56 ms 36064 KB Output is correct
5 Correct 69 ms 38596 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 36 ms 23324 KB Output is correct
11 Correct 35 ms 23916 KB Output is correct
12 Correct 57 ms 33352 KB Output is correct
13 Correct 71 ms 38104 KB Output is correct
14 Correct 58 ms 33220 KB Output is correct
15 Correct 61 ms 35264 KB Output is correct
16 Correct 55 ms 31920 KB Output is correct
17 Correct 66 ms 35520 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 23144 KB Output is correct
2 Correct 35 ms 23364 KB Output is correct
3 Correct 64 ms 29104 KB Output is correct
4 Correct 58 ms 28708 KB Output is correct
5 Correct 140 ms 39240 KB Output is correct
6 Correct 107 ms 39872 KB Output is correct
7 Correct 106 ms 39080 KB Output is correct
8 Correct 106 ms 40128 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 700 KB Output is correct
17 Correct 20 ms 5584 KB Output is correct
18 Correct 15 ms 7108 KB Output is correct
19 Correct 14 ms 6604 KB Output is correct
20 Correct 14 ms 6608 KB Output is correct
21 Correct 14 ms 6864 KB Output is correct
22 Correct 26 ms 13508 KB Output is correct
23 Correct 4 ms 1624 KB Output is correct
24 Correct 18 ms 4052 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 3 ms 1368 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 860 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 700 KB Output is correct
17 Correct 20 ms 5584 KB Output is correct
18 Correct 15 ms 7108 KB Output is correct
19 Correct 14 ms 6604 KB Output is correct
20 Correct 14 ms 6608 KB Output is correct
21 Correct 14 ms 6864 KB Output is correct
22 Correct 26 ms 13508 KB Output is correct
23 Correct 4 ms 1624 KB Output is correct
24 Correct 18 ms 4052 KB Output is correct
25 Correct 1 ms 600 KB Output is correct
26 Correct 3 ms 1368 KB Output is correct
27 Correct 3 ms 1372 KB Output is correct
28 Correct 62 ms 29036 KB Output is correct
29 Correct 99 ms 41396 KB Output is correct
30 Correct 144 ms 38980 KB Output is correct
31 Correct 109 ms 38468 KB Output is correct
32 Correct 87 ms 41928 KB Output is correct
33 Correct 108 ms 38196 KB Output is correct
34 Correct 116 ms 39352 KB Output is correct
35 Correct 49 ms 16204 KB Output is correct
36 Correct 105 ms 42052 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 23144 KB Output is correct
2 Correct 35 ms 23364 KB Output is correct
3 Correct 64 ms 29104 KB Output is correct
4 Correct 58 ms 28708 KB Output is correct
5 Correct 140 ms 39240 KB Output is correct
6 Correct 107 ms 39872 KB Output is correct
7 Correct 106 ms 39080 KB Output is correct
8 Correct 106 ms 40128 KB Output is correct
9 Correct 84 ms 35328 KB Output is correct
10 Correct 78 ms 22816 KB Output is correct
11 Correct 190 ms 45868 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 38 ms 23644 KB Output is correct
19 Correct 36 ms 23152 KB Output is correct
20 Correct 37 ms 23396 KB Output is correct
21 Correct 35 ms 23420 KB Output is correct
22 Correct 101 ms 34496 KB Output is correct
23 Correct 146 ms 45752 KB Output is correct
24 Correct 131 ms 41460 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 36504 KB Output is correct
2 Correct 63 ms 38596 KB Output is correct
3 Correct 35 ms 23148 KB Output is correct
4 Correct 35 ms 23652 KB Output is correct
5 Correct 127 ms 62900 KB Output is correct
6 Correct 252 ms 61100 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 81 ms 45932 KB Output is correct
9 Correct 95 ms 53436 KB Output is correct
10 Correct 56 ms 36064 KB Output is correct
11 Correct 69 ms 38596 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 36 ms 23324 KB Output is correct
17 Correct 35 ms 23916 KB Output is correct
18 Correct 57 ms 33352 KB Output is correct
19 Correct 71 ms 38104 KB Output is correct
20 Correct 58 ms 33220 KB Output is correct
21 Correct 61 ms 35264 KB Output is correct
22 Correct 55 ms 31920 KB Output is correct
23 Correct 66 ms 35520 KB Output is correct
24 Correct 35 ms 23144 KB Output is correct
25 Correct 35 ms 23364 KB Output is correct
26 Correct 64 ms 29104 KB Output is correct
27 Correct 58 ms 28708 KB Output is correct
28 Correct 140 ms 39240 KB Output is correct
29 Correct 107 ms 39872 KB Output is correct
30 Correct 106 ms 39080 KB Output is correct
31 Correct 106 ms 40128 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 1 ms 860 KB Output is correct
42 Correct 1 ms 604 KB Output is correct
43 Correct 1 ms 604 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 1 ms 604 KB Output is correct
46 Correct 1 ms 604 KB Output is correct
47 Correct 1 ms 700 KB Output is correct
48 Correct 20 ms 5584 KB Output is correct
49 Correct 15 ms 7108 KB Output is correct
50 Correct 14 ms 6604 KB Output is correct
51 Correct 14 ms 6608 KB Output is correct
52 Correct 14 ms 6864 KB Output is correct
53 Correct 26 ms 13508 KB Output is correct
54 Correct 4 ms 1624 KB Output is correct
55 Correct 18 ms 4052 KB Output is correct
56 Correct 1 ms 600 KB Output is correct
57 Correct 3 ms 1368 KB Output is correct
58 Correct 3 ms 1372 KB Output is correct
59 Correct 62 ms 29036 KB Output is correct
60 Correct 99 ms 41396 KB Output is correct
61 Correct 144 ms 38980 KB Output is correct
62 Correct 109 ms 38468 KB Output is correct
63 Correct 87 ms 41928 KB Output is correct
64 Correct 108 ms 38196 KB Output is correct
65 Correct 116 ms 39352 KB Output is correct
66 Correct 49 ms 16204 KB Output is correct
67 Correct 105 ms 42052 KB Output is correct
68 Correct 84 ms 35328 KB Output is correct
69 Correct 78 ms 22816 KB Output is correct
70 Correct 190 ms 45868 KB Output is correct
71 Correct 0 ms 344 KB Output is correct
72 Correct 0 ms 348 KB Output is correct
73 Correct 0 ms 348 KB Output is correct
74 Correct 1 ms 344 KB Output is correct
75 Correct 1 ms 348 KB Output is correct
76 Correct 0 ms 348 KB Output is correct
77 Correct 38 ms 23644 KB Output is correct
78 Correct 36 ms 23152 KB Output is correct
79 Correct 37 ms 23396 KB Output is correct
80 Correct 35 ms 23420 KB Output is correct
81 Correct 101 ms 34496 KB Output is correct
82 Correct 146 ms 45752 KB Output is correct
83 Correct 131 ms 41460 KB Output is correct
84 Correct 137 ms 58800 KB Output is correct
85 Correct 127 ms 62128 KB Output is correct
86 Correct 203 ms 59824 KB Output is correct
87 Correct 212 ms 61612 KB Output is correct
88 Correct 1 ms 348 KB Output is correct
89 Correct 227 ms 61876 KB Output is correct
90 Correct 173 ms 59328 KB Output is correct
91 Correct 154 ms 59820 KB Output is correct