제출 #1022790

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

fish

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

const int maxn = 1e5 + 100;
const int maxl = 11;
int n;
ll dp[maxn][maxl][maxl];
ll a[maxn][maxl];
ll pref[2][maxn];

long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
    n = N;
    if(*max_element(X.begin(), X.end()) <= 1 && n > 2){
        for(int i = 0; i < M; i++){
            Y[i]++;
            pref[X[i]][Y[i]] += W[i];
        }
        for(int i = 1; i <= n; i++){
            pref[0][i] += pref[0][i-1];
        }
        for(int i = n; i > 0; i--){
            pref[1][i] += pref[1][i+1];
        }
        ll ans = 0;
        for(int i = 0; i <= n; i++){
            ans = max(ans, pref[0][i] + pref[1][i+1]);
        }
        return ans;
    }
    bool ok = 0;
    ll sum[2] = {0, 0};
    for(int i = 0; i < M; i++){
        X[i]++; Y[i]++;
        if(Y[i] <= 11){
            a[X[i]][Y[i]] += W[i];
        } else{
            ok = 1;
            sum[X[i] & 1] += W[i];
        }
    }
    if(ok) return max(sum[0], sum[1]);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= 10; j++){
            a[i][j] += a[i][j-1];
        }
    }
    for(int c = 1; c <= n + 1; c++){
        for(int i = 0; i <= 10; i++){
            for(int j = 0; j <= 10; j++){
                dp[c][i][j] = -(ll)1e18;
                if(c == 1 && i == 0) dp[c][i][j] = 0;
            }
        }
    }
    for(int c = 2; c <= n + 1; c++){
        for(int i = 0; i <= 10; i++){
            for(int j = 0; j <= 10; j++){
                for(int k = 0; k <= 10; k++){
                    ll x = dp[c-1][i][j];
                    if(max(i, k) > j){
                        x += a[c-1][max(i, k)] - a[c-1][j];
                    }
                    dp[c][j][k] = max(dp[c][j][k], x);
                }
            }
        }
    }
    ll ans = 0;
    for(int i = 0; i <= 10; i++){
        ans = max(ans, dp[n+1][i][0]);
    }
    return ans;
}

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