Submission #729761

#	Time	Username	Problem	Language	Result	Execution time	Memory
729761		Nahian9696	Catfish Farm (IOI22_fish)	C++17	32 / 100	87 ms	21856 KiB

fish

#include "fish.h"

#include <vector>
#include <bits/stdc++.h>

using namespace std;


#define f0(i, n) for(int i = 0; i <  (n); i++)
#define f1(i, n) for(int i = 1; i <= (n); i++)
#define pb push_back
#define ff first
#define ss second

typedef vector<int> vi;
typedef long long ll;



long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    bool allxeven = true;
    bool allxleq1 = true;
    bool ally0 = true;

    f0(i, M) {
        if(X[i] % 2 == 1) allxeven = false;
        if(X[i] > 1) allxleq1 = false;
        if(Y[i] != 0) ally0 = false;
    }


    if (allxeven) {
        ll ret = 0;
        f0(i, M) ret += W[i];
        return ret;
    } 
    if(allxleq1) {
        ll ret = 0;
        ll ans = 0;
        int arr[N][2];
        f0(i, N) arr[i][0] = 0, arr[i][1] = 0;
        f0(i, M) {
            arr[Y[i]][X[i]] = W[i];
        }

        if(N == 2) {
            return max(arr[0][0] + arr[1][0], arr[0][1] + arr[1][1]);
        }

        f0(i, N) {
            ans += arr[i][1];
        }
        ret = ans;
        f0(i, N) {
            ans -= arr[i][1];
            ans += arr[i][0];
            ret = max(ret, ans);
        }
        return ret;
    }
    if(ally0) {
        int arr[N];
        f0(i, N) arr[i] = 0;
        f0(i, M) arr[X[i]] = W[i];
        ll dp[N][4];
        dp[0][0] = -1e18;
        dp[0][1] = -1e18;
        dp[0][2] = 0;
        dp[0][3] = arr[0];

        dp[1][0] = 0;
        dp[1][1] = arr[1];
        dp[1][2] = arr[0];
        dp[1][3] = -1e18;


        f1(i, N-2) {
            dp[i+1][0] = max(dp[i][0], dp[i][2]);
            dp[i+1][1] = max(dp[i][0], dp[i][2]) + arr[i+1];
            dp[i+1][2] = max(dp[i][1], dp[i][3]);
            dp[i+1][3] = dp[i][1] + arr[i+1];
        }
        return max({
            dp[N-1][0],
            dp[N-1][1],
            dp[N-1][2]
        });
    }


    ll arr[N][10];
    f0(i, N) f0(j, 10) arr[i][j] = 0;


    f0(i, M) {
        arr[X[i]][Y[i]+1] = W[i];
    }

    ll prefarr[N][10];
    f0(i, N) prefarr[i][0] = 0;

    f0(i, N) f1(j, 9) {
        prefarr[i][j] = prefarr[i][j-1] + arr[i][j];
    }

    ll dp[N][10][10][10];
    ll mxdp[N][10][10];

    f0(i, 10) f0(j, 10) {
        f0(k, 10) dp[0][i][j][k] = 0;
        mxdp[0][i][j] = 0;
    }


    f0(i, 10) f0(j, 10) {
        ll val = 0;
        if(i > j) {
            for(int x = j+1; x <= i; x++) val += arr[0][x];
        } else {
            for(int x = i+1; x <= j; x++) val += arr[1][x];
        }
        mxdp[1][i][j] = val;
        f0(k, 10) {
            dp[1][i][j][k] = val;
        }
    }


    f1(col, N-2) {
        f0(i, 10) f0(j, 10) {
            ll mx = 0;
            f0(k, 10) {
                dp[col+1][i][j][k] = mxdp[col][j][k];
                if(max(j, k) <= i) {
                    dp[col+1][i][j][k] += prefarr[col][i] - prefarr[col][max(j, k)];
                }
                if(j >= i) dp[col+1][i][j][k] += prefarr[col+1][j] - prefarr[col+1][i];
                mx = max(mx, dp[col+1][i][j][k]);
            }
            mxdp[col+1][i][j] = mx;
            // cout << mx << endl;
        }
    }

    ll ans = 0;
    f0(i, 10) f0(j, 10) ans = max(ans, mxdp[N-1][i][j]);

    return ans;

    return 9;
}

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