// #pragma GCC optimize("Ofast,O2,O3")
// #pragma GCC target("avx,avx2")
#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MP make_pair
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<pair<int, int>>> fish(N);
vector<vector<ll>> sum(N);
vector<vector<ll>> pref(N, vector<ll>(N + 1, 0));
for (int i = 0; i < M; i++){
++Y[i];
fish[X[i]].emplace_back(Y[i], W[i]);
pref[X[i]][Y[i]] += W[i];
}
for (int i = 0; i < N; i++){
for (int j = 1; j <= N; j++) pref[i][j] += pref[i][j - 1];
sort(fish[i].begin(), fish[i].end());
int k = (int)fish[i].size();
sum[i].resize(k);
for (int j = 0; j < k; j++){
sum[i][j] = fish[i][j].second;
if (j > 0) sum[i][j] += sum[i][j - 1];
}
}
function<ll(int, int, int)> get_sum = [&](int i, int l, int r){ // sum of fish with X = i, l <= Y <= r
if (l > r) return 0;
r = min(r, N);
l = max(l, 0);
return pref[i][r] - (l == 0 ? 0 : pref[i][l - 1]);
int pl = lower_bound(fish[i].begin(), fish[i].end(), MP(l, 0)) - fish[i].begin();
int pr = lower_bound(fish[i].begin(), fish[i].end(), MP(r + 1, 0)) - fish[i].begin() - 1;
if (pl > pr) return 0ll;
return sum[i][pr] - (pl > 0 ? sum[i][pl - 1] : 0ll);
};
vector<vector<ll>> dpl(N, vector<ll>(N + 1, 0));
for (int i = 1; i < N; i++){
for (int l = 0; l <= N; l++){
for (int j = 0; j <= N; j++){
dpl[i][l] = max(dpl[i][l], dpl[i - 1][j] + get_sum(i - 1, j + 1, l));
}
for (int j = 0; j <= N; j++){
if (i >= 2) dpl[i][l] = max(dpl[i][l], dpl[i - 2][j] + get_sum(i - 1, 1, max(l, j)));
}
}
}
vector<vector<ll>> dpr(N, vector<ll>(N + 1, 0));
for (int i = N - 2; i >= 0; i--){
for (int l = 0; l <= N; l++){
for (int j = 0; j <= N; j++){
dpr[i][l] = max(dpr[i][l], dpr[i + 1][j] + get_sum(i + 1, j + 1, l));
}
for (int j = 0; j <= N; j++){
if (i + 2 < N) dpr[i][l] = max(dpr[i][l], dpr[i + 2][j] + get_sum(i + 1, 1, max(l, j)));
}
}
}
ll res = 0;
for (int i = 0; i < N; i++){
for (int l = 0; l <= N; l++){
res = max(res, dpl[i][l] + dpr[i][l]);
}
}
for (int i = 0; i + 1 < N; i++){
for (int l1 = 0; l1 <= N; l1++){
for (int l2 = 0; l2 <= N; l2++){
ll cur = dpl[i][l1] + dpr[i + 1][l2];
cur += get_sum(i, l1 + 1, l2);
cur += get_sum(i + 1, l2 + 1, l1);
res = max(res, cur);
}
}
}
for (int i = 1; i + 1 < N; i++){
for (int l1 = 0; l1 <= N; l1++){
for (int l2 = 0; l2 <= N; l2++){
ll cur = dpl[i - 1][l1] + dpr[i + 1][l2];
cur += get_sum(i, 1, max(l1, l2));
res = max(res, cur);
}
}
}
for (int i = 1; i + 2 < N; i++){
for (int l1 = 0; l1 <= N; l1++){
for (int l2 = 0; l2 <= N; l2++){
ll cur = dpl[i - 1][l1] + dpr[i + 2][l2];
cur += get_sum(i, 1, l1);
cur += get_sum(i + 1, 1, l2);
res = max(res, cur);
}
}
}
return res;
}
Compilation message
fish.cpp: In lambda function:
fish.cpp:40:27: error: inconsistent types 'int' and 'long long int' deduced for lambda return type
40 | return pref[i][r] - (l == 0 ? 0 : pref[i][l - 1]);
fish.cpp:44:29: error: inconsistent types 'int' and 'long long int' deduced for lambda return type
44 | if (pl > pr) return 0ll;
| ^~~
fish.cpp:45:27: error: inconsistent types 'int' and 'long long int' deduced for lambda return type
45 | return sum[i][pr] - (pl > 0 ? sum[i][pl - 1] : 0ll);
