제출 #1129079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129079		vladilius	메기 농장 (IOI22_fish)	C++20	35 / 100	1171 ms	1883540 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

ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
    int n = N, m = M;
    for (int i = 0; i < m; i++){
        X[i]++; Y[i]++;
    }
    vector<int> d[n + 1];
    for (int i = 0; i < m; i++){
        d[X[i]].pb(i);
    }
    
    vector<vector<ll>> F(n + 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];
        }
    }
    
    auto f = [&](int i, int l, int r){
        return F[i][r] - F[i][l - 1];
    };
    
    vector<vector<vector<ll>>> dp(n + 1, vector<vector<ll>>(n + 1, vector<ll>(2)));
    for (int i = 2; i <= n; i++){
        for (int j = 0; j <= n; j++){
            // dp[i][j][0]
            for (int k = 0; k <= j; k++){
                dp[i][j][0] = max(dp[i][j][0], dp[i - 1][k][0] + f(i - 1, k + 1, j));
            }
            if (i > 2){
                for (int t = 0; t <= j; t++){
                    dp[i][j][0] = max(dp[i][j][0], max(dp[i - 2][t][0], dp[i - 2][t][1]) + f(i - 1, 1, j));
                }
                for (int t = j + 1; t <= n; t++){
                    dp[i][j][0] = max(dp[i][j][0], max(dp[i - 2][t][0], dp[i - 2][t][1]) + f(i - 1, 1, t));
                }
            }
            
            // dp[i][j][1]
            for (int k = j + 1; k <= n; k++){
                dp[i][j][1] = max(dp[i][j][1], max(dp[i - 1][k][0], dp[i - 1][k][1]) + f(i, j + 1, k));
            }
        }
    }
    ll out = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j <= n; j++){
            out = max({out, dp[i][j][0], dp[i][j][1]});
        }
    }
    return out;
}

• 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