Submission #1216686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216686		duckindog	매우 즐거운 카드 게임 (JOI15_cardgame2)	C++20	100 / 100	53 ms	4424 KiB

cardgame2

#include <bits/stdc++.h>

using namespace std;

const int N = 500 + 10;
int n;
int c[N], a[N], v[N];

long long pref[N];
long long f[N][N][2];

inline void getMax(auto& x, const auto& y) { 
    x = max(x, y);
}

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> c[i] >> a[i] >> v[i];

    for (int i = 1; i <= n + 1; ++i) pref[i] = pref[i - 1] + v[i];

    auto sum = [&](int l, int r) { 
        return pref[r] - pref[l - 1];
    };
    auto chk = [&](int i, int j) { 
        return c[i] == c[j] || a[i] == a[j];
    };

    long long answer = 0;

    memset(f, -14, sizeof f);
    f[1][2][0] = f[1][2][1] = 0;
    for (int i = 1; i <= n; ++i) { 
        for (int j = i + 1; j <= n + 1; ++j) { 
            for (int type = 0; type <= 1; ++type) { 
                const auto& cur = f[i][j][type];

                if (!type) {
                    long long value = cur + sum(i, i); 
                    getMax(answer, value);

                    if (chk(i, j)) getMax(f[j][j + 1][0], value);
                    if (chk(i, j + 2)) getMax(f[j][j + 1][1], value);
                } else { 
                    for (int k = j + 1; k <= n; ++k) { 
                        long long value = cur + sum(j + 1, k);
                        answer = max(answer, value);

                        if (chk(i, k)) { 
                            long long value1 = value + sum(i, i);
                            answer = max(answer, value1);

                            if (chk(i, j)) getMax(f[j][k + 1][0], value1);
                            if (chk(i, k + 2)) getMax(f[j][k + 1][1], value1);
                        }

                        if (!chk(k, k + 1)) break;
                    }
                }
            }
        }
    }
    

    cout << answer << "\n";
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 75 / 75