제출 #1079444

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1079444		asdasdqwer	메기 농장 (IOI22_fish)	C++17	53 / 100	1071 ms	2097152 KiB

fish

#include "fish.h"
#include <bits/stdc++.h>
using namespace std;

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
    // first subtask
    bool s1 = true, s2=true, s3 = true;
    for (int i=0;i<M;i++) {
        if (X[i] % 2 != 0) s1=false;
        if (X[i] > 1) s2=false;
        if (Y[i] != 0) s3 = false;
    }
    if (s1) {
        long long sm = 0;
        for (int i=0;i<M;i++) sm += W[i];
        return sm;
    }


    if (s2) {
        long long sm1=0,sm2=0;
        for (int i=0;i<M;i++) {
            if (X[i] == 0) sm1 += W[i];
            else sm2 += W[i];
        }
        if (N == 2) return max(sm1, sm2);

        vector<long long> p(N, 0), s(N, 0);
        for (int i=0;i<M;i++) {
            if (X[i] == 0) p[Y[i]] += W[i];
            else s[Y[i]] += W[i];
        }

        for (int i=1;i<N;i++) p[i]+=p[i-1];
        for (int i=N-2;i>=0;i--) s[i] += s[i+1];

        long long mx = max(p[N-1], s[0]);
        for (int i=1;i<N;i++) {
            mx = max(mx, p[i-1]+s[i]);
        }

        return mx;
    }

    if (s3) {
        vector<int> w(N,0);
        for (int i=0;i<M;i++) {
            w[X[i]] = W[i];
        }

        vector<long long> dp1(N, 0), dp2(N, 0), dp3(N, 0);
        dp1[0] = dp2[0] = dp3[0] = 0;
        for (int i=1;i<N;i++) {
            // build smt
            dp1[i] = max(dp1[i-1], max(dp2[i-1], dp3[i-1] + w[i-1]));
            dp2[i] = max(dp1[i-1] + w[i], max(dp2[i-1], dp3[i-1]));
            dp3[i] = max(dp3[i-1], dp2[i-1]);
        }

        return max(dp1.back(), max(dp2.back(), dp3.back()));
    }
    
    vector<vector<long long>> dp1(N, vector<long long>(N+1, 0)), dp2(N, vector<long long>(N+1, 0));
    // dp1[i][j] : maximum number of fish such that row i has pier with height j
    // dp2[i][j] : maximum number of fish such that row i has pier with height j and row i-1 has pier with height no greater than j

    vector<vector<long long>> s(N, vector<long long>(N+1, 0));
    for (int i=0;i<M;i++) {
        s[X[i]][Y[i]+1] = W[i];
    }

    for (int i=N-1;i>=0;i--) {
        for (int j=N-1;j>=0;j--) {
            s[i][j] += s[i][j+1];
        }
    }

    long long mx = 0;

    for (int i=1;i<N;i++) {
        for (int j=0;j<=N;j++) {
            long long sub = (j == N ? 0 : s[i-1][j+1]);
            for (int k=0;k<=j;k++) {
                dp1[i][j] = max(dp1[i][j], max(dp2[i-1][k] + (k == N ? 0 : s[i-1][k+1]) - sub, dp1[i-1][k]));
            }
            dp2[i][j] = dp1[i][j];
            sub = (j == N ? 0 : s[i][j+1]);
            for (int k=j+1;k<=N;k++) {
                dp1[i][j] = max(dp1[i][j], max(dp1[i-1][k], dp2[i-1][k]) + sub - (k == N ? 0 : s[i][k+1]));
            }

            mx = max(mx, max(dp1[i][j], dp2[i][j]));
        }
    }

    return mx;
}

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