#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const ll oo = 1e18;
void cmax(ll& a, ll b) {a=max(a,b);}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
vvi ys(N+1);
bool allEven=1;
ll total=0;
for(int i=0;i<M;++i) {
if(X[i]%2!=0) allEven=0;
Y[i]++,X[i]++;
total+=W[i];
ys[X[i]].push_back(i);
}
vector<vector<ll>> pref(N+1,{0});
{
int x=0;
for(auto& v : ys) {
sort(all(v),[&](int i, int j) {return Y[i]<Y[j];});
for(auto& id : v) {
pref[x].push_back(W[id]);
id = Y[id];
}
pref[x].push_back(0);
v.insert(v.begin(),0);
v.push_back(N+1);
partial_sum(all(pref[x]),pref[x].begin());
assert(pref[x].size()==v.size());
x++;
}
}
// dynamic programming
// DP[column][y-pos][state]
// state {0: rising, 1: falling}
// transition going up:
array<vector<ll>,2> dp = {vector<ll>{0LL,-oo},{-oo,-oo}};
ll top = -oo;
auto getS = [&](int x, int y) {
auto i = max(0LL,upper_bound(all(ys[x]),y)-ys[x].begin()-1LL);
return pref[x][i];
};
for(int x=1;x<=N;++x) {
int k = ys[x].size();
array<vector<ll>,2> ndp = {vector<ll>(k,-oo),vector<ll>(k,-oo)};
// falling to falling
{
int j = ys[x-1].size()-1;
ll best = -oo;
for(int i=k-1;i>=0;--i) {
while(j>=0 and ys[x-1][j]>=ys[x][i]) {
cmax(best,dp[1][j]);
--j;
}
cmax(ndp[1][i], best-getS(x-1,ys[x][i]) + pref[x][i]);
}
}
// rising to rising
{
int j = 0;
ll best = -oo;
for(int i=0;i<k;++i) {
while(j<int(ys[x-1].size()) and ys[x-1][j]<=ys[x][i]) {
cmax(best,dp[0][j]-getS(x,ys[x-1][j]));
++j;
}
cmax(ndp[0][i], best + pref[x][i]);
}
}
// falling to rising, far apart
{
ll best = *max_element(all(dp[1]));
for(int i=0;i<k;++i)
cmax(ndp[0][i],best+pref[x][i]);
}
// falling to rising, case 2
// {
// int j = 0;
// ll best = -oo;
// for(int i=0;i<k;++i) {
// while(j<int(ys[x-1].size()) and ys[x-1][j]<=ys[x][i]) {
// cmax(best,dp[1][j]-getS(x,ys[x-1][j])-pref[x-1][j]);
// ++j;
// }
// cmax(ndp[0][i], best + pref[x][i] + getS(x-1, ys[x][i]));
// }
}
// top to falling
for(int i=0;i<k;++i) {
cmax(ndp[1][i],pref[x][i]+top);
}
// rising to top
cmax(top,*max_element(all(dp[0])));
cmax(top,*max_element(all(dp[1])));
swap(dp,ndp);
}
// falling or top
auto ans = max(top,*max_element(all(dp[1])));;
assert(ans<=total);
return ans;
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:101:23: error: 'k' was not declared in this scope
101 | for(int i=0;i<k;++i) {
| ^
fish.cpp:102:18: error: 'ndp' was not declared in this scope; did you mean 'dp'?
102 | cmax(ndp[1][i],pref[x][i]+top);
| ^~~
| dp
fish.cpp:102:33: error: 'x' was not declared in this scope
102 | cmax(ndp[1][i],pref[x][i]+top);
| ^
fish.cpp:107:17: error: 'ndp' was not declared in this scope; did you mean 'dp'?
107 | swap(dp,ndp);
| ^~~
| dp
fish.cpp: At global scope:
fish.cpp:110:20: error: 'top' was not declared in this scope
110 | auto ans = max(top,*max_element(all(dp[1])));;
| ^~~
fish.cpp:110:41: error: 'dp' was not declared in this scope
110 | auto ans = max(top,*max_element(all(dp[1])));;
| ^~
fish.cpp:4:22: note: in definition of macro 'all'
4 | #define all(x) begin(x),end(x)
| ^
fish.cpp:110:41: error: 'dp' was not declared in this scope
110 | auto ans = max(top,*max_element(all(dp[1])));;
| ^~
fish.cpp:4:29: note: in definition of macro 'all'
4 | #define all(x) begin(x),end(x)
| ^
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from fish.cpp:2:
fish.cpp:111:5: error: expected unqualified-id before 'static_cast'
111 | assert(ans<=total);
| ^~~~~~
fish.cpp:111:5: error: expected ')' before 'static_cast'
fish.cpp:112:5: error: expected unqualified-id before 'return'
112 | return ans;
| ^~~~~~
fish.cpp:114:1: error: expected declaration before '}' token
114 | }
| ^
