oj.uz

답안 #1055118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1055118 2024-08-12T14:40:18 Z ProtonDecay314 메기 농장 (IOI22_fish) C++17
0 / 100
 750 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], dpdec[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

# 결과 실행 시간 메모리 Grader output
1 Runtime error 750 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 726 ms 2097152 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 686 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 1 ms 516 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 604 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 1 ms 516 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 604 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 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 1 ms 516 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 604 KB 1st lines differ - on the 1st token, expected: '216624184325', found: '214837477243'
10 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 686 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 750 ms 2097152 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -