#include "fish.h"
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
vvii fishes;
int weightSum(int x, int y1, int y2) {
if (x >= fishes.size() || y2 <= y1)
return 0;
int res = 0;
for (auto [y, w] : fishes[x]) {
if (y1 <= y && y < y2)
res += w;
}
return res;
}
long long max_weights(signed N, signed M, vector<signed> X, std::vector<signed> Y, std::vector<signed> W) {
fishes = vvii(N);
loop(i, M) {
fishes[X[i]].push_back({Y[i], W[i]});
}
fishes.push_back({});
loop(x, N) {
sort(all(fishes[x]));
}
vector<map<int, int>> before(N);
vector<map<int, int>> both(N);
//bestBefore, bestBeforeAndAfter
loop(x, N) {
if (x == 0) {
for (auto [y, w] : fishes[x + 1]) {
both[0][y + 1] = weightSum(x + 1, 0, y + 1);
}
before[0][0] = 0;
continue;
}
set<ii> heights;
for (auto [y, w] : fishes[x - 1]) {
heights.insert({y, w});
}
for (auto [y, w] : fishes[x + 1]) {
heights.insert({y, w});
}
int bestBefore2 = 0;
int bestBoth3 = 0;
if (x >= 2) {
for (auto [prevY, prevScore] : before[x - 2])
bestBefore2 = max(bestBefore2, prevScore);
}
if (x >= 3) {
for (auto [prevY, prevScore] : both[x - 3])
bestBoth3 = max(bestBoth3, prevScore);
}
for (auto [y, w] : heights) {
for (auto [prevY, prevScore] : before[x - 1]) {
both[x][y + 1] = max(both[x][y + 1], prevScore + weightSum(x - 1, prevY, y + 1) + weightSum(x + 1, 0, y + 1));
before[x][y + 1] = max(before[x][y + 1], prevScore + weightSum(x - 1, prevY, y + 1));
}
for (auto [prevY, prevScore] : both[x - 1]) {
both[x][y + 1] = max(both[x][y + 1], prevScore + weightSum(x + 1, 0, y + 1) - weightSum(x, 0, min(prevY, y + 1)) + weightSum(x - 1, prevY, y + 1));
before[x][y + 1] = max(before[x][y + 1], prevScore - weightSum(x, 0, min(prevY, y + 1)) + weightSum(x - 1, prevY, y + 1));
}
both[x][y + 1] = max(both[x][y + 1], bestBefore2 + weightSum(x - 1, 0, y + 1) + weightSum(x + 1, 0, y + 1));
both[x][y + 1] = max(both[x][y + 1], bestBoth3 + weightSum(x - 1, 0, y + 1) + weightSum(x + 1, 0, y + 1));
before[x][y + 1] = max(before[x][y + 1], bestBefore2 + weightSum(x - 1, 0, y + 1));
before[x][y + 1] = max(before[x][y + 1], bestBoth3 + weightSum(x - 1, 0, y + 1));
}
}
int res = 0;
loop(x, N) {
for (auto [y, score] : before[x]) {
res = max(res, score);
}
for (auto [y, score] : both[x]) {
res = max(res, score);
}
}
return res;
}
signed main() {
cout << max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3}) << endl;
return 0;
}
Compilation message
fish.cpp: In function 'long long int weightSum(long long int, long long int, long long int)':
fish.cpp:35:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | if (x >= fishes.size() || y2 <= y1)
| ~~^~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccnH5JvJ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccYoTcFI.o:fish.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
