oj.uz

Submission #1055177

# Submission time Handle Problem Language Result Execution time Memory
1055177 2024-08-12T15:05:07 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]);
                    }
                }
            }
        }

        // 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 780 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 749 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 716 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 1 ms 348 KB Output is correct
2 Correct 0 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 1520 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 1212 KB Output is correct
13 Correct 1 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 1 ms 348 KB Output is correct
2 Correct 0 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 1520 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 1212 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 752 KB Output is correct
17 Correct 50 ms 6200 KB Output is correct
18 Correct 57 ms 7884 KB Output is correct
19 Correct 36 ms 7376 KB Output is correct
20 Correct 36 ms 7376 KB Output is correct
21 Correct 40 ms 7600 KB Output is correct
22 Correct 130 ms 13772 KB Output is correct
23 Correct 4 ms 2392 KB Output is correct
24 Correct 18 ms 4820 KB Output is correct
25 Correct 1 ms 1372 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 1 ms 348 KB Output is correct
2 Correct 0 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 1520 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 1212 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 1372 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 752 KB Output is correct
17 Correct 50 ms 6200 KB Output is correct
18 Correct 57 ms 7884 KB Output is correct
19 Correct 36 ms 7376 KB Output is correct
20 Correct 36 ms 7376 KB Output is correct
21 Correct 40 ms 7600 KB Output is correct
22 Correct 130 ms 13772 KB Output is correct
23 Correct 4 ms 2392 KB Output is correct
24 Correct 18 ms 4820 KB Output is correct
25 Correct 1 ms 1372 KB Output is correct
26 Correct 4 ms 2140 KB Output is correct
27 Correct 33 ms 72016 KB Output is correct
28 Correct 530 ms 33660 KB Output is correct
29 Execution timed out 1032 ms 110252 KB Time limit exceeded
30 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

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