#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()); } ll mx=0; for(int i=1;i<=N;i++){ 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; } } 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][r]); if(i>=2)dp[i][j]=max(dp[i][j],dp[i-2][j]+ps[i-1][r]); mx=max(mx,dp[i][j]); } } } return mx; }