#include "fish.h" #include<bits/stdc++.h> using namespace std; #include <vector> #define ll long long #define ff first #define ss second #define pb push_back vector<pair<ll,ll>>vc[500]; long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W) { vector< vector<ll>> dp(N+10, vector<ll>(N+10)); for(int i=0;i<=N;i++)vc[i].clear(); for(int i=0;i<M;i++){ vc[X[i]+1].pb({Y[i]+1,W[i]}); } vector<vector<vector<ll>>> ps(N+10, vector<vector<ll>>(N+10, vector<ll>(N+10) ) ); for(int i=1;i<=N;i++){ for(int l=1;l<=N;l++){ int s=0; int idx=0; for(int r=l;r<=N;r++){ while(idx<vc[i].size() and vc[i][idx].ff<=r){ s+=vc[i][idx++].ss; } ps[i][l][r]=s; } } } ll mx=0; for(int i=1;i<=N;i++){ for(int j=0;j<=N;j++){ for(int k=0;k<=N;k++){ int l=min(i,j),r=max(i,j); dp[i][j]=max(dp[i][j],dp[i-1][j]+ps[i-1][1][r]-ps[i-1][1][l-1]); if(i>=2)dp[i][j]=max(dp[i][j],dp[i-2][j]+ps[i-1][1][r]); mx=max(mx,dp[i][j]); } } } return mx; }