Submission #671286

#	Time	Username	Problem	Language	Result	Execution time	Memory
671286		tbzard	Catfish Farm (IOI22_fish)	C++17	52 / 100	1098 ms	260384 KiB

fish

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, int> piipi;
typedef pair<pii, pii> piipii;

#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

ll dp[3005][3005][3]; // A(a), (A)a, (A)
ll pref[2][3005];
int pos[3005][3005];
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
    for(int i=0;i<sz(x);i++) pos[x[i]+1][y[i]+1] = w[i];
    memset(dp, -1, sizeof(dp));

    ll ans = 0;
    for(int i=1;i<=n;i++){
        memset(pref, 0, sizeof(pref));
        for(int j=1;j<=n;j++){
            pref[0][j] = pref[0][j-1] + pos[i-1][j];
            pref[1][j] = pref[1][j-1] + pos[i][j];
        }
        if(i == 1){
            for(int j=0;j<=n;j++) dp[i][j][2] = 0;
        }
        else{
            // 0
            ll mx = -1e18;
            for(int j=n;j>=0;j--){
                if(dp[i-1][j][0] != -1) mx = max(mx, dp[i-1][j][0] + pref[1][j]);
                if(dp[i-1][j][2] != -1) mx = max(mx, dp[i-1][j][2] + pref[1][j]);
                dp[i][j][0] = max(dp[i][j][0], mx - pref[1][j]);
            }

            // 1
            for(int j=n;j>=0;j--){
                dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][0] + pref[1][j]);
                dp[i][j][1] = max(dp[i][j][1], dp[i-1][j][2] + pref[1][j]);
            }


            // 2
            ll mx0 = -1e18, mx1 = -1e18;
            for(int j=0;j<=n;j++){
                if(dp[i-1][j][0] != -1) mx0 = max(mx0, dp[i-1][j][0]);
                if(dp[i-1][j][1] != -1) mx1 = max(mx1, dp[i-1][j][1] - pref[0][j]);
                if(dp[i-1][j][2] != -1) mx1 = max(mx1, dp[i-1][j][2] - pref[0][j]);
                dp[i][j][2] = max(dp[i][j][2], mx0);
                dp[i][j][2] = max(dp[i][j][2], mx1 + pref[0][j]);
            }
        }

        ll sum = 0;
        for(int j=0;j<=n;j++){
            sum += pos[i+1][j];
            ans = max(ans, dp[i][j][0] + sum);
            ans = max(ans, dp[i][j][2] + sum);
        }
    }

    return ans;
}

• 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