Submission #1129092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129092		vladilius	Catfish Farm (IOI22_fish)	C++20	38 / 100	1123 ms	1540904 KiB

fish

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll infm = -1e18;

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
    int n = N, m = M;
    bool ind = 1;
    int T = 0;
    for (int i = 0; i < m; i++){
        if (X[i] % 2){
            ind = 0;
        }
        X[i]++; Y[i]++;
        T = max(T, X[i]);
    }
    
    if (ind){
        ll out = 0;
        for (int i: W){
            out += i;
        }
        return out;
    }
    
    vector<int> d[n + 1];
    for (int i = 0; i < m; i++){
        d[X[i]].pb(i);
    }
    
    T = min(T + 1, n);
    vector<vector<ll>> F(T + 1, vector<ll>(n + 1));
    for (int i = 1; i <= n; i++){
        for (int j: d[i]){
            F[i][Y[j]] = W[j];
        }
        for (int j = 1; j <= n; j++){
            F[i][j] += F[i][j - 1];
        }
    }

    vector<vector<vector<ll>>> dp(T + 1, vector<vector<ll>>(n + 1, vector<ll>(2)));
    for (int i = 2; i <= T; i++){
        vector<ll> pr1(n + 1), pr2(n + 1), pr3(n + 2);
        pr1[0] = pr2[0] = infm;
        for (int j = 0; j <= n; j++){
            if (j != 0){
                pr1[j] = pr1[j - 1];
                pr2[j] = pr2[j - 1];
            }
            pr1[j] = max(pr1[j], dp[i - 1][j][0] - F[i - 1][j]);
            if (i > 2){
                pr2[j] = max(pr2[j], max(dp[i - 2][j][0], dp[i - 2][j][1]));
            }
        }
        if (i > 2){
            for (int j = n; j >= 0; j--){
                pr3[j] = max(pr3[j + 1], max(dp[i - 2][j][0], dp[i - 2][j][1]) + F[i - 1][j]);
            }
        }
        vector<ll> pr4(n + 2);
        for (int j = n; j >= 0; j--){
            pr4[j] = max(pr4[j + 1], max(dp[i - 1][j][0], dp[i - 1][j][1]) + F[i][j]);
        }
        for (int j = 0; j <= n; j++){
            dp[i][j][0] = pr1[j] + F[i - 1][j];
            if (i > 2){
                dp[i][j][0] = max(dp[i][j][0], pr2[j] + F[i - 1][j]);
                dp[i][j][0] = max(dp[i][j][0], pr3[j + 1]);
            }
            dp[i][j][1] = max(0LL, pr4[j + 1] - F[i][j]);
        }
    }
    ll out = 0;
    for (int i = 1; i <= T; i++){
        for (int j = 0; j <= n; j++){
            out = max({out, dp[i][j][0], dp[i][j][1]});
        }
    }
    return out;
}

• Subtask 1: 3 / 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