#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; ++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";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |