제출 #629278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
629278		qwerasdfzxcl	메기 농장 (IOI22_fish)	C++17	18 / 100	828 ms	132180 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll INF = 4e18;
vector<int> H[100100], A[100100];
vector<ll> dp[2][100100], S[100100], prf[2][100100], suf[2][100100];
int n, sz[100100];

ll cost(int i, int s, int e){
    if (s>e || i==0) return 0;
    int j1 = upper_bound(H[i].begin(), H[i].end(), s-1) - H[i].begin() - 1;
    int j2 = upper_bound(H[i].begin(), H[i].end(), e) - H[i].begin() - 1;
    return S[i][j2] - S[i][j1];
}

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W) {
    n = N;
    for (int i=0;i<=N;i++) {H[i].push_back(0); H[i].push_back(N);}
    for (int i=0;i<M;i++){
        ++X[i], ++Y[i];
        H[X[i]].push_back(Y[i]);
        H[X[i]].push_back(Y[i]-1);
        if (X[i]>1) H[X[i]-1].push_back(Y[i]);
        if (X[i]<N) H[X[i]+1].push_back(Y[i]);
    }


    for (int i=0;i<=N;i++){
        sort(H[i].begin(), H[i].end());
        H[i].erase(unique(H[i].begin(), H[i].end()), H[i].end());
        sz[i] = H[i].size();

        A[i].resize(sz[i], 0);
        S[i].resize(sz[i], 0);
        dp[0][i].resize(sz[i], 0);
        dp[1][i].resize(sz[i], 0);
        prf[0][i].resize(sz[i]);
        prf[1][i].resize(sz[i]);
        suf[0][i].resize(sz[i]);
        suf[1][i].resize(sz[i]);
    }

    for (int i=0;i<M;i++){
        int idx = lower_bound(H[X[i]].begin(), H[X[i]].end(), Y[i]) - H[X[i]].begin();
        assert(idx < sz[X[i]]);
        A[X[i]][idx] = W[i];
    }


    for (int i=1;i<=n;i++){
        for (int j=1;j<sz[i];j++) S[i][j] = S[i][j-1] + A[i][j];
    }


    dp[0][0][0] = 0;
    dp[1][0][0] = 0;
    assert(sz[0]==2);
    dp[0][0][1] = -INF;
    dp[1][0][1] = -INF;

    for (int i=1;i<=n;i++){
        --i;
        for (int j=0;j<sz[i];j++){
            prf[0][i][j] = dp[0][i][j] + cost(i, H[i][j]+1, n);
            prf[1][i][j] = max(dp[0][i][j], dp[1][i][j]);
            suf[0][i][j] = max(dp[0][i][j], dp[1][i][j]) + cost(i+1, 1, H[i][j]);
            suf[1][i][j] = dp[1][i][j] + cost(i+1, 1, H[i][j]);

            if (j==0) continue;
            prf[0][i][j] = max(prf[0][i][j], prf[0][i][j-1]);
            prf[1][i][j] = max(prf[1][i][j], prf[1][i][j-1]);
            suf[0][i][j] = max(suf[0][i][j], suf[0][i][j-1]);
            suf[1][i][j] = max(suf[1][i][j], suf[1][i][j-1]);
        }
        ++i;

        for (int j=0;j<sz[i];j++){
            ///0 -> 0
            int idx00 = upper_bound(H[i-1].begin(), H[i-1].end(), H[i][j]) - H[i-1].begin() - 1;
            dp[0][i][j] = max(dp[0][i][j], prf[0][i-1][idx00] - cost(i-1, H[i][j]+1, n));
            /*for (int k=0;k<sz[i-1] && H[i-1][k]<=H[i][j];k++){
                dp[0][i][j] = max(dp[0][i][j], dp[0][i-1][k] + cost(i-1, H[i-1][k]+1, H[i][j]));
            }*/

            ///1 -> 0
            if (i>=2){
                int idx10 = upper_bound(H[i-2].begin(), H[i-2].end(), H[i][j]) - H[i-2].begin() - 1;
                dp[0][i][j] = max(dp[0][i][j], prf[1][i-2][idx10] + cost(i-1, 1, H[i][j]));
                if (idx10+1 < sz[i-2]) dp[0][i][j] = max(dp[0][i][j], suf[0][i-2][idx10+1]);

                /*for (int k=0;k<sz[i-2];k++){
                    dp[0][i][j] = max(dp[0][i][j], max(dp[0][i-2][k], dp[1][i-2][k]) + cost(i-1, 1, max(H[i-2][k], H[i][j])));
                }*/
            }

            ///0 -> 1
            dp[1][i][j] = max(dp[1][i][j], dp[0][i-1][sz[i-1]-1] + cost(i, H[i][j]+1, n));

            ///1 -> 1
            int idx11 = lower_bound(H[i-1].begin(), H[i-1].end(), H[i][j]) - H[i-1].begin();
            dp[1][i][j] = max(dp[1][i][j], suf[1][i-1][idx11] - cost(i, 1, H[i][j]));
            //for (int k=0;k<sz[i-1];k++) if (H[i-1][k] >= H[i][j]) dp[1][i][j] = max(dp[1][i][j], dp[1][i-1][k] + cost(i, H[i][j]+1, H[i-1][k]));
        }
    }

    //printf(" %lld %lld %lld\n", H[1][0], H[1][1], H[1][2]);
    //printf(" %lld -> %lld(%d)\n", cost(1, 1, 1), dp[0][2][1], H[2][1]);

    return max(*max_element(dp[0][n].begin(), dp[0][n].end()), *max_element(dp[1][n].begin(), dp[1][n].end()));
}

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