#include<bits/stdc++.h>
using namespace std;
const int N = 500 + 5;
const long long inf = 1e18;
bool dp[N][N][N];
int n,c[N],a[N],v[N];
long long p[N];
void solve()
{
cin>>n;
for(int i=1;i<=n;++i) cin>>c[i]>>a[i]>>v[i];
c[n+1]=c[n+2]=c[n+3]=c[n];
a[n+1]=a[n+2]=a[n+3]=a[n];
for(int i=1;i<=n+3;++i) p[i]=p[i-1]+v[i];
dp[3][1][2]=1;
long long ans=0;
for(int k=3;k<=n+3;++k){
for(int i=1;i<=n;++i){
for(int j=1;j<=n;++j) if(dp[k][i][j]){
// cout<<i<<' '<<j<<' '<<k<<' '<<dp[k][i][j]<<'\n';
if(i<j)
{
ans=max(ans,p[k-1]-v[i]-v[j]);
if(k==3 || c[i]==c[k-1] || a[i]==a[k-1]) dp[k+1][j][i]=1;
if(k==3 || c[k-1]==c[k] || a[k-1]==a[k]) dp[k+1][i][j]=1;
}
else
{
int ni=i,nj=k-1,nk=k,lst=j;
ans=max(ans,p[nk-1]-v[ni]-v[nj]);
// cout<<ni<<' '<<nj<<' '<<nk<<'\n';
if(c[ni]==c[lst] || a[ni]==a[lst]) dp[nk+1][nj][ni]=1;
if(c[nk]==c[lst] || a[nk]==a[lst]) dp[nk+1][ni][nj]=1;
}
}
}
}
cout<<ans;
}
int main(void)
{
// freopen(TASK".inp","r",stdin);
// freopen(TASK".out","w",stdout);
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int testcase=1;
// cin>>testcase;
while(testcase--)
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |