oj.uz

Submission #1055187

# Submission time Handle Problem Language Result Execution time Memory
1055187 2024-08-12T15:12:04 Z ProtonDecay314 Catfish Farm (IOI22_fish) C++17
35 / 100
 1000 ms 2097152 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();

        L(j, 0ll, f1s) {
            L(k, 0ll, f2s) {
                if(fax1[j].y < fax2[k].y) continue; // Decreasing, skip

                dpinc[i][j] = max(dpinc[i][j], dpinc[i - 1ll][k] + psum[i - 1ll][fax1[j].y] - psum[i - 1ll][fax2[k].y]);
                // if(fax2[k].y == 0ll && i > 1ll) {
                //     L(l, 0ll, f3s) {
                //         ll max_y = max(fax1[j].y, fax3[l].y);
                //         dpinc[i][j] = max(dpinc[i][j], max(dpdec[i - 2ll][l], dpinc[i - 2ll][l]) + psum[i - 1ll][max_y]);
                //     }
                // }
            }

            if(i > 1ll) {
                L(l, 0ll, f3s) {
                    dpinc[i][j] = max(dpinc[i][j], max(dpdec[i - 2ll][l], dpinc[i - 2ll][l]) + psum[i - 1ll][max(fax1[j].y, fax3[l].y)]);
                }
            }
        }

        // Then decreasing
        L(j, 0ll, f1s) {
            L(k, 0ll, f2s) {
                if(fax1[j].y > fax2[k].y) continue; // Increasing, skip

                dpdec[i][j] = max(dpdec[i][j], max(dpinc[i - 1ll][k], dpdec[i - 1ll][k]) + psum[i][fax2[k].y] - psum[i][fax1[j].y]);
            }

            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
0 / 3.0

# Verdict Execution time Memory Grader output
1 Runtime error 862 ms 2097152 KB Execution killed with signal 9
2 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 Runtime error 812 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 800 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 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 Correct 0 ms 604 KB Output is correct
10 Correct 2 ms 1372 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 1368 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 1372 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 1 ms 348 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 Correct 0 ms 604 KB Output is correct
10 Correct 2 ms 1372 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 1368 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1112 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 41 ms 6400 KB Output is correct
18 Correct 46 ms 7888 KB Output is correct
19 Correct 36 ms 7376 KB Output is correct
20 Correct 33 ms 7372 KB Output is correct
21 Correct 35 ms 7376 KB Output is correct
22 Correct 103 ms 13768 KB Output is correct
23 Correct 4 ms 2388 KB Output is correct
24 Correct 20 ms 4820 KB Output is correct
25 Correct 1 ms 1368 KB Output is correct
26 Correct 4 ms 2140 KB Output is correct

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 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 Correct 0 ms 604 KB Output is correct
10 Correct 2 ms 1372 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 1368 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1112 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 41 ms 6400 KB Output is correct
18 Correct 46 ms 7888 KB Output is correct
19 Correct 36 ms 7376 KB Output is correct
20 Correct 33 ms 7372 KB Output is correct
21 Correct 35 ms 7376 KB Output is correct
22 Correct 103 ms 13768 KB Output is correct
23 Correct 4 ms 2388 KB Output is correct
24 Correct 20 ms 4820 KB Output is correct
25 Correct 1 ms 1368 KB Output is correct
26 Correct 4 ms 2140 KB Output is correct
27 Correct 33 ms 72016 KB Output is correct
28 Correct 416 ms 33660 KB Output is correct
29 Execution timed out 1059 ms 111540 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 800 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 862 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -