#include <bits/stdc++.h> using namespace std; #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, vector<int> X, vector<int> Y, vector<int> W) { vector<vector<ll>> dp(N+2, vector<ll>(N+2, 0)); vector<vector<ll>> ps(N+2, vector<ll>(N+2, 0)); 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]}); } // 🔴 REQUIRED: sort by Y 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; // build prefix sums for row i for(int l = 1; l <= N; l++){ ps[i][l] = ps[i][l-1]; while(idx < (int)vc[i].size() && vc[i][idx].ff <= l){ ps[i][l] += vc[i][idx].ss; idx++; } } // DP transitions for(int j = 0; j <= N; j++){ int l = min(i, j); int r = max(i, j); dp[i][j] = max(dp[i][j], dp[i-1][j] + ps[i-1][r] - ps[i-1][l-1]); 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; }