#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
const ll inf = 1e16;
ll max_weights( int n, int m, vector<int> x, vector<int> y, vector<int> w ){
vector<vector<pii>> v(n);
vector<vector<ll>> sv(n);
for( int i = 0; i < m; i++ ) v[x[i]].push_back({ y[i], w[i] });
for( int i = 0; i < n; i++ ){
v[i].push_back({ -1, 0 });
v[i].push_back({ n, 0 });
sort( v[i].begin(), v[i].end() );
sv[i].resize(v[i].size());
for( int j = 1; j < (int)sv[i].size(); j++ ) sv[i][j] = sv[i][j - 1] + v[i][j].second;
}
vector<vector<vector<ll>>> dp( n );
for( int i = 0; i < n; i++ ) dp[i].resize(v[i].size(), vector<ll>(2));
for( int i = 0; i < n; i++ ){
int k = v[i].size();
for( int j = k - 1; j >= 0; j-- ){
auto [pos, val] = v[i][j];
if( i == 0 ){ dp[i][j][0] = 0; continue; }
if( j + 1 == k ){ dp[i][j][0] = dp[i - 1][v[i - 1].size() - 1][1]; continue; }
int id_next = upper_bound( v[i - 1].begin(), v[i - 1].end(), pii( pos, inf ) ) - v[i - 1].begin();
dp[i][j][0] = max( dp[i][j + 1][0], dp[i - 1][id_next][0] + sv[i][j] - sv[i - 1][id_next - 1] );
}
for( int j = 0; j < k; j++ ){
auto [pos, val] = v[i][j];
if( i == 0 ){ dp[i][j][1] = sv[i][j]; continue; }
if( j == 0 ){ dp[i][j][1] = dp[i - 1][0][0]; continue; }
int id_next = upper_bound( v[i - 1].begin(), v[i - 1].end(), pii( pos, -inf ) ) - v[i - 1].begin();
dp[i][j][1] = max({ dp[i][j - 1][1] + val, dp[i - 1][id_next][0] + sv[i][j], dp[i - 1][id_next - 1][1] + val });
}
}
return dp[n - 1][0][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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |