#include <bits/stdc++.h>
using namespace std;
#include "fish.h"
int const Mx = 1e5 + 10;
long long n , m;
map<int , int>cost[Mx] , vis[Mx];
vector<int>possible[Mx];
vector<long long>pref[Mx] , dp[3][Mx];
long long max_weights(int N, int M , vector<int> X, vector<int> Y, vector<int> W) {
m = M , n = N;
long long ans = 0 , Sum = 0;
int MaxX = 0 , Even = 1;
for(int i = 0 ; i < m ; ++i) {
++X[i];
++Y[i];
Sum += W[i];
if(X[i] % 2 == 0) Even = 0;
MaxX = max(MaxX , X[i]);
if(vis[X[i] - 1][Y[i]] == 0) possible[X[i] - 1].push_back(Y[i]);
if(vis[X[i] + 1][Y[i]] == 0) possible[X[i] + 1].push_back(Y[i]);
if(vis[X[i]][Y[i]] == 0) possible[X[i]].push_back(Y[i]);
vis[X[i] - 1][Y[i]] = 1;
vis[X[i] + 1][Y[i]] = 1;
vis[X[i]][Y[i]] = 1;
cost[X[i]][Y[i]] = W[i];
}
if(Even) return Sum;
for(int i = 1 ; i <= n ; ++i) {
possible[i].push_back(0);
sort(possible[i].begin() , possible[i].end());
for(auto j : possible[i]) {
long long cur = 0;
if(pref[i].size()) cur = pref[i].back();
cur += cost[i][j];
pref[i].push_back(cur);
dp[0][i].push_back(0);
dp[1][i].push_back(0);
}
}
if(MaxX <= 2) {
if(n == 2) return max(pref[1].back() , pref[2].back());
long long sum = pref[2].back();
int Req = 0;
for(int j = 0 ; j < possible[1].size() ; ++j) {
while(Req + 1 < possible[2].size() && possible[2][Req + 1] <= possible[1][j]) ++Req;
ans = max(ans , sum - pref[2][Req] + pref[1][j]);
}
return ans;
}
for(int i = 2 ; i <= n ; ++i) {
for(int J = 0 ; J < possible[i].size() ; ++J) {
int j = possible[i][J];
int Req1 = 0 , Req2 = 0;
while(Req1 + 1 < possible[i - 1].size() && possible[i - 1][Req1 + 1] <= j) ++Req1;
for(int K = 0 ; K < possible[i - 1].size() ; ++K) {
int k = possible[i - 1][K];
while(Req2 + 1 < possible[i].size() && possible[i][Req2 + 1] <= k) ++Req2;
if(k <= j) dp[0][i][J] = max(dp[0][i][J] , dp[0][i - 1][K] + pref[i - 1][Req1] - pref[i - 1][K]);
else dp[1][i][J] = max(dp[1][i][J] , max(dp[0][i - 1][K] , dp[1][i - 1][K]) + pref[i][Req2] - pref[i][J]);
}
if(i >= 3) {
int Req = 0;
for(int K = 0 ; K < possible[i - 2].size() ; ++K) {
int k = possible[i - 2][K];
while(Req + 1 < possible[i - 1].size() && possible[i - 1][Req + 1] <= max(j , k)) ++Req;
dp[0][i][J] = max(dp[0][i][J] , max(dp[0][i - 2][K] , dp[1][i - 2][K]) + pref[i - 1][Req]);
}
}
ans = max(ans , dp[0][i][J]);
ans = max(ans , dp[1][i][J]);
}
}
return ans;
}
/*
3 4
1 1 5
1 2 10
2 1 5
3 1 5
*/
Compilation message
towers.cpp:3:10: fatal error: fish.h: No such file or directory
3 | #include "fish.h"
| ^~~~~~~~
compilation terminated.
