#include "fish.h"
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <array>
#include <algorithm>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <random>
#include <cstdlib>
#define debug(x) std::cout << #x << " " << (x) << '\n';
#define pb push_back
#define mp std::make_pair
#define remax(a, b) a = std::max((a), (b));
#define remin(a, b) a = std::min((a), (b));
#define maxWeights max_weights
int64_t solveSmallN(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
std::vector<int32_t> w) {
const int32_t MAX_N = 300;
std::array<std::array<int64_t, MAX_N>, MAX_N> wPrefSums {};
std::array<std::array<std::array<int64_t, 3>, MAX_N + 1>, MAX_N + 1> dp {};
auto getWRangeSum = [&wPrefSums](int32_t startRow, int32_t endRow, int32_t column) -> int64_t {
if(endRow <= startRow) {
return 0;
}
return wPrefSums[endRow - 1][column] - (startRow == 0 ? 0 : wPrefSums[startRow - 1][column]);
};
for(int32_t i = 0; i < m; i++) {
wPrefSums[y[i]][x[i]] = (int64_t) w[i];
}
for(int32_t j = 0; j < n; j++) {
for(int32_t i = 1; i < n; i++) {
wPrefSums[i][j] += wPrefSums[i - 1][j];
}
}
for(int32_t j = 1; j < n; j++) {
for(int32_t lastK = 0; lastK <= n; lastK++) {
for(int32_t k = 0; k <= n; k++) {
if(k == 0) {
remax(dp[j + 1][lastK][2], dp[j][lastK][0] + getWRangeSum(0, lastK, j));
remax(dp[j + 1][lastK][2], dp[j][lastK][1] + getWRangeSum(0, lastK, j));
}
if(lastK <= k) {
remax(dp[j + 1][k][0], dp[j][lastK][0] + getWRangeSum(lastK, k, j - 1));
remax(dp[j + 1][k][0], dp[j][lastK][2] + getWRangeSum(lastK, k, j - 1));
}
if(lastK >= k) {
remax(dp[j + 1][k][1], dp[j][lastK][1] + getWRangeSum(k, lastK, j));
remax(dp[j + 1][k][1], dp[j][lastK][0] + getWRangeSum(k, lastK, j));
remax(dp[j + 1][k][0], dp[j][lastK][2]);
}
}
}
}
int64_t ans = 0;
for(int32_t k = 0; k <= n; k++) {
remax(ans, dp[n][k][0]);
remax(ans, dp[n][k][1]);
remax(ans, dp[n][k][2]);
}
return ans;
}
int64_t solveEvenXs(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
std::vector<int32_t> w) {
int64_t ans = 0;
for(int32_t i = 0; i < m; i++) {
ans += (int64_t) w[i];
}
return ans;
}
int64_t solveAllXs0Or1(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
std::vector<int32_t> w) {
const int32_t MAX_N = 1e5;
std::array<std::array<int64_t, 2>, MAX_N> wPrefSums {};
auto getWRangeSum = [&wPrefSums](int32_t startRow, int32_t endRow, int32_t column) -> int64_t {
if(endRow <= startRow) {
return 0;
}
return wPrefSums[endRow - 1][column] - (startRow == 0 ? 0 : wPrefSums[startRow - 1][column]);
};
for(int32_t i = 0; i < m; i++) {
wPrefSums[y[i]][x[i]] = (int64_t) w[i];
}
for(int32_t j = 0; j < 2; j++) {
for(int32_t i = 1; i < n; i++) {
wPrefSums[i][j] += wPrefSums[i - 1][j];
}
}
int64_t ans = 0;
remax(ans, getWRangeSum(0, n, 1));
remax(ans, getWRangeSum(0, n, 0));
if(n > 2) {
for(int32_t i = 0; i <= n; i++) {
remax(ans, getWRangeSum(0, i, 0) + getWRangeSum(i, n, 1));
}
}
return ans;
}
int64_t solveAllYs0(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> w) {
const int32_t MAX_N = 1e5;
std::array<int32_t, MAX_N + 3> wByColumn {};
for(int32_t i = 0; i < m; i++) {
wByColumn[x[i]] = w[i];
}
if(n == 2) {
return std::max(wByColumn[0], wByColumn[1]);
}
std::array<std::array<std::array<int64_t, 2>, 2>, MAX_N + 3> dp {};
dp[2][0][0] = 0;
dp[2][0][1] = wByColumn[0];
dp[2][1][0] = 0;
dp[2][1][1] = 0;
for(int32_t j = 2; j <= n + 1; j++) {
for(int32_t p = 0; p < 2; p++) {
for(int32_t q = 0; q < 2; q++) {
remax(dp[j + 1][q][0], dp[j][p][q] + ((p == 1 && q != 1) ? wByColumn[j - 1] : 0));
remax(dp[j + 1][q][1], dp[j][p][q] + (q != 1 ? wByColumn[j - 1] : 0));
}
}
}
return dp[n + 2][0][0];
}
int64_t solveMediumN(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
std::vector<int32_t> w) {
const int32_t MAX_N = 3000;
std::array<std::array<int64_t, MAX_N>, MAX_N> wPrefSums{};
auto getWRangeSum = [&wPrefSums](int32_t startRow, int32_t endRow, int32_t column) -> int64_t {
if(endRow <= startRow) {
return 0;
}
return wPrefSums[endRow - 1][column] - (startRow == 0 ? 0 : wPrefSums[startRow - 1][column]);
};
for(int32_t i = 0; i < m; i++) {
wPrefSums[y[i]][x[i]] = (int64_t) w[i];
}
for(int32_t j = 0; j < n; j++) {
for(int32_t i = 1; i < n; i++) {
wPrefSums[i][j] += wPrefSums[i - 1][j];
}
}
std::array<int64_t, MAX_N + 1> dpIncr{}, dpDecr{}, nDpIncr{}, nDpDecr{};
dpIncr.fill(-1e18);
dpDecr.fill(-1e18);
dpIncr[0] = 0;
dpDecr[0] = 0;
for(int32_t j = 1; j <= n + 1; j++) {
for(int32_t k = 0; k <= n; k++) {
nDpIncr[k] = dpDecr[0];
for(int32_t lastK = 0; lastK <= k; lastK++) {
remax(nDpIncr[k], dpIncr[lastK] + getWRangeSum(lastK, k, j - 1));
}
nDpDecr[k] = -1e18;
for(int32_t lastK = k; lastK <= n; lastK++) {
remax(nDpDecr[k], dpDecr[lastK] + getWRangeSum(k, lastK, j));
remax(nDpDecr[k], dpIncr[lastK] + getWRangeSum(k, lastK, j));
}
}
dpIncr = nDpIncr;
dpDecr = nDpDecr;
}
return std::max(dpIncr[0], dpDecr[0]);
}
int64_t maxWeights(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
std::vector<int32_t> w) {
if(n <= 3000) {
return solveMediumN(n, m, x, y, w);
}
else if(std::all_of(x.begin(), x.end(), [](int32_t v) { return !(v & 1); })) {
return solveEvenXs(n, m, x, y, w);
}
else if(std::all_of(x.begin(), x.end(), [](int32_t v) { return (v < 2); })) {
return solveAllXs0Or1(n, m, x, y, w);
}
else if(std::all_of(y.begin(), y.end(), [](int32_t v) { return (v == 0); })) {
return solveAllYs0(n, m, x, w);
}
return 0;
}
Compilation message
fish.cpp:27:20: error: ambiguating new declaration of 'int64_t max_weights(int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>)'
27 | #define maxWeights max_weights
| ^~~~~~~~~~~
fish.cpp:213:9: note: in expansion of macro 'maxWeights'
213 | int64_t maxWeights(int32_t n, int32_t m, std::vector<int32_t> x, std::vector<int32_t> y,
| ^~~~~~~~~~
In file included from fish.cpp:1:
fish.h:3:11: note: old declaration 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)'
3 | long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
| ^~~~~~~~~~~
