oj.uz

Submission #1055245

# Submission time Handle Problem Language Result Execution time Memory
1055245 2024-08-12T15:52:19 Z ProtonDecay314 Catfish Farm (IOI22_fish) C++17
0 / 100
 103 ms 55212 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;

        L(j, 0ll, f1s) {
            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
                cur_pref_dpinc_max += (ll)fax2[f2i].w;

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

                f2i++;
            }
            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--;
            }
            dpdec[i][j] = max(dpdec[i][j], cur_suff_dpdec_max);
        }

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

        // 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;
}

Compilation message

fish.cpp: In function 'll max_weights(int, int, vi, vi, vi)':
fish.cpp:98:50: warning: unused variable 'f3s' [-Wunused-variable]
   98 |         ll f1s = fax1.size(), f2s = fax2.size(), f3s = fax3.size();
      |                                                  ^~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 34240 KB Output is correct
2 Correct 54 ms 37572 KB Output is correct
3 Correct 29 ms 23660 KB Output is correct
4 Correct 29 ms 23404 KB Output is correct
5 Incorrect 103 ms 55212 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '89874348830048'
6 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 67 ms 42904 KB 1st lines differ - on the 1st token, expected: '40604614618209', found: '40604944491929'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23392 KB Output is correct
2 Correct 32 ms 23660 KB Output is correct
3 Incorrect 53 ms 28700 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 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 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '93823316002'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 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 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '93823316002'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 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 Incorrect 0 ms 348 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '93823316002'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 23392 KB Output is correct
2 Correct 32 ms 23660 KB Output is correct
3 Incorrect 53 ms 28700 KB 1st lines differ - on the 1st token, expected: '21261825233649', found: '26722970331638'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 34240 KB Output is correct
2 Correct 54 ms 37572 KB Output is correct
3 Correct 29 ms 23660 KB Output is correct
4 Correct 29 ms 23404 KB Output is correct
5 Incorrect 103 ms 55212 KB 1st lines differ - on the 1st token, expected: '149814460735479', found: '89874348830048'
6 Halted 0 ms 0 KB -