#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<int,int>>vc[310]; 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)); vector< vector<ll>> ps(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]}); } for(int i=1;i<=N;i++){ sort(vc[i].begin(),vc[i].end()); int idx=0; for(int l=1;l<=N;l++){ ps[i][l]=ps[i][l-1]; while(idx<vc[i].size() and vc[i][idx].ff<=l){ ps[i][l]+=vc[i][idx++].ss; } } } 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(k,j),r=max(k,j); if(k>j){ dp[i][j]=max(dp[i][j],dp[i-1][k]+ps[i][k]-ps[i][j]); } dp[i][j]=max(dp[i][j],dp[i-1][k]+ps[i-1][r]-ps[i-1][l-1] ); if(i>=2)dp[i][j]=max(dp[i][j],dp[i-2][k]+ps[i-1][r]); mx=max(mx,dp[i][j]); } } } return mx; }