#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint,lint> ii;
struct state{
lint h, P, D, I;
bool operator < (state &b){
return this->h < b.h;
}
bool operator == (state &b){
return this->h == b.h;
}
};
vector<state> dp[200005];
vector<ii> sum[200005];
///get the sum of values in column x, up to height H
inline lint getsum(int x, lint H){
if(x == -1) return 0;
auto it = upper_bound(all(sum[x]), ii(H, 1023456678901234LL));
if(it == sum[x].begin()) return 0;
it--;
return it->second;
}
long long max_weight(int n, int m, vector<int> X, vector<int> Y, vector<int> C){
if(n == 1) return 0;
///setting up sum counts
for(int i = 0;i < m;i++){
sum[X[i]].push_back(ii(Y[i], C[i]));
}
for(int i = 0;i < n;i++){
sort(all(sum[i]));
for(int j = 1;j < sz(sum[i]);j++){
sum[i][j].second += sum[i][j-1].second;
}
}
///set up the important values in the dp table
for(int i = 0;i < m;i++){
if(X[i] != 0) dp[X[i]-1].push_back({Y[i], 0, 0, 0});
if(X[i] != n-1) dp[X[i]+1].push_back({Y[i], 0, 0, 0});
}
for(int i = 0;i < n;i++){
dp[i].push_back({-1,0,0,0}); ///represent not taking anything
sort(all(dp[i]));
dp[i].erase(unique(all(dp[i])), dp[i].end());
}
///now do dp
for(auto &s : dp[0]){
s.P = getsum(1, s.h);
s.I = -getsum(0, s.h);
s.D = getsum(1, s.h) - getsum(0, s.h);
}
for(int i = 1;i < n;i++){
///I to I and I to P
lint bestI = 0;
auto it = dp[i-1].begin();
for(auto &s : dp[i]){
while(it != dp[i-1].end()){
if(it->h >= s.h){
bestI = max(bestI, it->I);
it++;
}
else break;
}
///I to I
s.I = max(s.I, bestI + getsum(i-1, s.h) - getsum(i, s.h));
///I to P
s.P = max(s.P, bestI + getsum(i-1, s.h) + getsum(i+1, s.h));
}
///D to D and P to D
reverse(all(dp[i]));
reverse(all(dp[i-1]));
lint bestPD = 0;
it = dp[i-1].begin();
for(auto &s : dp[i]){
while(it != dp[i-1].end()){
if(it->h <= s.h){
bestPD = max(bestPD, it->P);
bestPD = max(bestPD, it->D);
it++;
}
else break;
}
///D to D and P to D
s.D = max(s.D, bestPD + getsum(i+1, s.h) - getsum(i, s.h));
}
reverse(all(dp[i]));
reverse(all(dp[i-1]));
///D -1 to I -1
dp[i][0].I = max(dp[i][0].I, dp[i-1][0].D);
///P to P 2 spaces away
if(i >= 2){
lint bestP = 0;
for(auto &s : dp[i-2]) bestP = max(bestP, s.P);
for(auto &s : dp[i]){
s.P = max(s.P, bestP + getsum(i+1, s.h));
}
}
}
lint ans = 0;
for(int i = 0;i < n;i++){
/*
show(i);
for(auto s : dp[i]){
cerr << s.h << ": ";
show3(s.P, s.I, s.D);
}
cerr << endl << endl;
//*/
for(auto &s : dp[i]){
ans = max(ans, s.P);
ans = max(ans, s.I);
ans = max(ans, s.D);
}
}
return ans;
}
Compilation message
/usr/bin/ld: /tmp/ccFLQXU4.o: in function `main':
grader.cpp:(.text.startup+0x25e): undefined reference to `max_weights(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
