Submission #1161830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161830		KK_1729	메기 농장 (IOI22_fish)	C++17	52 / 100	960 ms	2162688 KiB

fish

#include "fish.h"

#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"

void printVector(vector<long long> a){

    for (auto x: a) cout << x << " ";
    cout << endl;
}
long long max(long long x, long long y){
    if (x > y) return x;

    else return y;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {


    vector<vector<pair<int, int>>> o(N);
    FOR(i,0,M) o[X[i]].pb({Y[i], W[i]});
    FOR(i,0,N) sort(all(o[i]));
    vector<vector<long long>> dp1(N+1, vector<long long>(N+1)); // when it is currently increasing
    vector<vector<long long>> dp2(N+1, vector<long long>(N+1)); // when it is currently decreasing

    vector<vector<long long>> prefix(N+1, vector<long long>(N+1));
    FOR(i,0,N){
        for (auto item: o[i]) prefix[i][item.first] = item.second;
        FOR(j,1,N) prefix[i][j] += prefix[i][j-1];
    }
    long long answer = 0;
    FOR(i,1,N){

        long long c = 0ll;
        FOR(j,0,N){
            c = max(c, dp1[i-1][j]-prefix[i-1][j]);
            dp1[i][j] = max(dp1[i-1][j], prefix[i-1][j]+c);
        }

        if (i > 1){ // Case where there is no pier in (i-1)
            c = dp2[i-2][N];
            FOR(j,0,N){
                c = max(c, dp1[i-2][j]);
                dp1[i][j] = max(dp1[i][j], prefix[i-1][j]+c);
            }
            c = 0;
            for (int j = N-1; j >= 0; j--){
                c = max(c, max(dp1[i-2][j], dp2[i-2][j])+prefix[i-1][j]);
                dp1[i][j] = max(dp1[i][j], c);
            }
            dp1[i][N] = dp1[i-1][N];
        }
        

        long long d = 0ll;
        for (int j = N-1; j >= 0; j--){
            d = max(d, dp2[i-1][j]+prefix[i][j]);
            d = max(d, dp1[i-1][j]+prefix[i][j]);
            dp2[i][j] = max(dp2[i][j], d-prefix[i][j]);
        }

        long long u = 0ll;
        FOR(j,0,N) u = max(u, max(dp1[i-1][j], dp2[i-1][j])+prefix[i][j]);
        u = max(u, dp2[i-1][N]);
        dp2[i][N] = u;
        FOR(j,0,N+1) answer = max(answer, dp1[i][j]);
        FOR(j,0,N+1) answer = max(answer, dp2[i][j]);
        // printVector(dp1[i]);
        // printVector(dp2[i]);
        // cout << endl;
    }




    return answer;
}

• Subtask 1: 0 / 3
• Subtask 2: 0 / 6
• Subtask 3: 0 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 0 / 14
• Subtask 8: 0 / 16