Submission #770198

#	Time	Username	Problem	Language	Result	Execution time	Memory
770198		jlallas384	Catfish Farm (IOI22_fish)	C++17	35 / 100	1125 ms	2097152 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

long long max_weights(int n, int m, vector<int> x, vector<int> y,
                      vector<int> w) { 
    vector<vector<int>> g(n + 1, vector<int>(n + 2));
    for(int i = 0; i < m; i++){
        g[y[i] + 1][x[i] + 1] = w[i];
    }
    vector<vector<ll>> dpl(n + 1, vector<ll>(n + 1, -1e9)), dpr(n + 1, vector<ll>(n + 1, -1e9)); // dp1 = take left only, dp2 = take left and right
    dpl[0][0] = dpr[0][0] = 0;
    ll pre = 0;
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ll ls = 0, rs = 0;

        ll rsub = 0;
        if(i >= 3){
            for(int j = 0; j <= n; j++){
                pre = max({pre, dpl[j][i - 3], dpr[j][i - 3]});
            }
        }
        for(int j = 0; j <= n; j++){
            ls += g[j][i - 1];
            rs += g[j][i + 1];
            rsub += g[j][i];

            ll sub = 0;
            for(int k = 0; k <= j; k++){
                sub += g[k][i - 1];
                dpl[j][i] = max(dpl[j][i], dpl[k][i - 1] + ls - sub);
                dpr[j][i] = max(dpr[j][i], dpl[k][i - 1] + ls + rs - sub);
            }

            for(int k = j; k <= n; k++){
                dpr[j][i] = max(dpr[j][i], dpr[k][i - 1] + rs - rsub);
            }

            if(i >= 2){
                sub = 0;
                for(int k = 0; k <= j; k++){
                    sub += g[k][i - 1];
                    dpl[j][i] = max(dpl[j][i], dpr[k][i - 2] + ls - sub);
                    dpr[j][i] = max(dpr[j][i], dpr[k][i - 2] + ls + rs - sub);
                }
            }

            dpl[j][i] = max(dpl[j][i], pre + ls);
            dpr[j][i] = max(dpr[j][i], pre + ls + rs);

            ans = max({ans, dpl[j][i], dpr[j][i]});
        }
    }
    return ans;
}

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