제출 #1129106

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1129106		vladilius	메기 농장 (IOI22_fish)	C++20	70 / 100	1174 ms	1839704 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 Tx = 0, Ty = 0;
    for (int i = 0; i < m; i++){
        if (X[i] % 2){
            ind = 0;
        }
        X[i]++; Y[i]++;
        Tx = max(Tx, X[i]);
        Ty = max(Ty, Y[i]);
    }
    
    if (ind){
        ll out = 0;
        for (int i: W){
            out += i;
        }
        return out;
    }
    
    Tx = min(Tx + 1, n);
    Ty = min(Ty + 1, n);
    
    vector<int> d[n + 1], dy[n + 1];
    for (int i = 0; i < m; i++){
        d[X[i]].pb(i);
        dy[X[i]].pb(Y[i]);
    }
    for (int i = 1; i <= n; i++){
        sort(dy[i].begin(), dy[i].end());
        dy[i].pb(Ty + 1);
    }
    
    vector<vector<ll>> F(Tx + 1, vector<ll>(Ty + 1));
    for (int i = 1; i <= Tx; i++){
        for (int j: d[i]){
            F[i][Y[j]] = W[j];
        }
        for (int j = 1; j <= Ty; j++){
            F[i][j] += F[i][j - 1];
        }
    }

    vector<vector<vector<ll>>> dp(Tx + 1, vector<vector<ll>>(Ty + 1, vector<ll>(2)));
    for (int i = 2; i <= Tx; i++){
        vector<ll> pr1(Ty + 1), pr2(Ty + 1), pr3(Ty + 2);
        pr1[0] = pr2[0] = infm;
        for (int j = 0; j <= Ty; 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 = Ty; 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(Ty + 2);
        for (int j = Ty; 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 x: dy[i]){
            int j = x - 1;
            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 <= Tx; i++){
        for (int j = 0; j <= Ty; j++){
            out = max({out, dp[i][j][0], dp[i][j][1]});
        }
    }
    return out;
}

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