제출 #1022918

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1022918		vjudge1	메기 농장 (IOI22_fish)	C++17	35 / 100	1089 ms	205160 KiB

fish

#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second

const int MAXN = 300100;
int n, w[MAXN], m;
pii a[MAXN];

namespace A{
    ll solve(){
        ll ans = 0;
        for(int i=1; i<=m; i++){
            ans += w[i];
        }
        return ans;
    }
}

namespace B{
    ll d[3001][3001];
    ll dp[3001][3001];
    ll pref[3001][3001];
    ll ddp[3001][3001];
    ll solve(){
        int mxh = 0;
        for(int i=1; i<=m; i++){
            d[a[i].ff][a[i].ss] += w[i];
            mxh = max(mxh, a[i].ss);
        }
        for(int i=1; i<=n; i++){
            dp[0][i] = -1e18;
            ddp[0][i] = -1e18;
        }
        dp[0][0] = 0;
        ddp[0][0] = 0;
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                pref[i][j] = pref[i][j - 1] + d[i][j];
            }
            for(int j=0; j<=mxh; j++){
                ddp[i][j] = 0;
                dp[i][j] = 0;
                for(int k=0; k<=j; k++){
                    ddp[i][j] = max(ddp[i][j], ddp[i-1][k] + pref[i-1][j]-pref[i-1][k]);
                }
                for(int k=0; k<=mxh; k++){
                    ddp[i][j] = max(ddp[i][j], dp[i-1][k]);
                }
                dp[i][j] = ddp[i][j];
                for(int k=j; k<=mxh; k++){
                    dp[i][j] = max(dp[i][j], dp[i-1][k] + pref[i][k] - pref[i][j]);
                }
                for(int k=0; k<=j; k++){
                    dp[i][j] = max(dp[i][j], ddp[i-1][k] + pref[i-1][j] - pref[i-1][k]);
                }
                if(i < 2) continue;
                for(int k=0; k<=mxh; k++){
                    dp[i][j] = max(dp[i][j], dp[i-2][k] + pref[i-1][max(k, j)]);
                }
            }
        }
        //for(int i=1; i<=n; i++){
        //    for(int j=0; j<=n; j++){
        //        cout<<dp[i][j]<<' ';
        //    }
        //    cout<<'\n';
        //}
        ll ans = 0;
        for(int i=0; i<=n; i++) ans = max(ans, dp[n][i]);
        return ans;
    }
}

long long max_weights(int N, int M, vector<int> X, vector<int> Y,
                      vector<int> W) {
    n = N;
    m = M;
    for(int i=1; i<=m; i++){
        a[i] = {X[i-1]+1, Y[i-1]+1};
    }
    for(int i=1; i<=m; i++){
        w[i] = W[i-1];
    }
    int ok1 = 1;
    for(int i=1; i<=m; i++){
        ok1 &= (a[i].ff % 2 == 0);
    }
    if(ok1) return A::solve();
    return B::solve();
    return 0;
}

• 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