#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 ll 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;
vector<vector<pair<int, ll>>> fishes;
vector<map<int, ll>> prefixWeight;
inline ll 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;
auto it1 = prefixWeight[x].upper_bound(y2 - 1);
auto it2 = prefixWeight[x].upper_bound(y1 - 1);
ll res = (--it1)->second - (--it2)->second;
//cout << x << ' ' << y1 << ' ' << y2 << " = " << res << endl;
return res;
}
long long max_weights(signed N, signed M, vector<signed> X, std::vector<signed> Y, std::vector<signed> W) {
fishes = vector<vector<pair<int, ll>>>(N);
loop(i, M) {
fishes[X[i]].push_back({Y[i], W[i]});
}
fishes.push_back({});
prefixWeight = vector<map<int, ll>>(N + 1);
loop(x, N + 1) {
sort(all(fishes[x]));
ll total = 0;
prefixWeight[x][-2] = 0;
for (auto [y, w] : fishes[x]) {
total += w;
prefixWeight[x][y] = total;
}
}
vector<map<int, ll>> beforeDp(N);
vector<map<int, ll>> bothDp(N);
vector<ll> maxBefore(N);
vector<ll> maxBoth(N);
//bestBefore, bestBeforeAndAfter
loop(x, N) {
if (x == 0) {
for (const auto& [y, w] : fishes[x + 1]) {
bothDp[0][y + 1] = weightSum(x + 1, 0, y + 1);
maxBoth[x] = max(maxBoth[x], bothDp[0][y + 1]);
}
beforeDp[0][0] = 0;
maxBefore[0] = 0;
continue;
}
ll bestBefore2 = 0;
ll bestBoth3 = 0;
if (x >= 2) {
bestBefore2 = maxBefore[x - 2];
}
if (x >= 3) {
bestBoth3 = maxBoth[x - 3];
}
int counter = 0;
for (const auto& [y, w] : fishes.at(x - 1)) {
int height = y + 1;
ll& both = bothDp[x][height];
ll& before = beforeDp[x][height];
for (const auto& [prevHeight, prevScore] : beforeDp.at(x - 1)) {
counter++;
int prevCur = weightSum(x - 1, prevHeight, height);
both = max(both, prevScore + prevCur);
before = max(before, prevScore + prevCur);
}
for (const auto& [prevY, prevScore] : bothDp.at(x - 1)) {
//counter++;
if (prevY <= height)
continue;
int prevCur = -weightSum(x, 0, height);
both = max(both, prevScore + prevCur);
}
int prevWeight = weightSum(x - 1, 0, height);
both = max(both, bestBefore2 + prevWeight);
both = max(both, bestBoth3 + prevWeight);
before = max(before, bestBefore2 + prevWeight);
before = max(before, bestBoth3 + prevWeight);
maxBefore[x] = max(maxBefore[x], before);
}
for (const auto& [y, w] : fishes.at(x + 1)) {
int height = y + 1;
ll& both = bothDp[x][height];
for (const auto& [prevHeight, prevScore] : beforeDp.at(x - 1)) {
counter++;
int prevCur = weightSum(x - 1, prevHeight, height);
both = max(both, prevScore + prevCur);
}
for (const auto& [prevY, prevScore] : bothDp.at(x - 1)) {
//counter++;
if (prevY <= height)
continue;
int prevCur = -weightSum(x, 0, height);
both = max(both, prevScore + prevCur);
}
int prevWeight = weightSum(x - 1, 0, height);
both = max(both, bestBefore2 + prevWeight);
both = max(both, bestBoth3 + prevWeight);
}
for (const auto& [height, score] : bothDp.at(x)) {
counter++;
int nextWeight = weightSum(x + 1, 0, height);
bothDp[x][height] += nextWeight;
maxBoth[x] = max(maxBoth[x], bothDp[x][height]);
}
cout << "Counter: " << counter << endl;
ll& both = bothDp[x][0];
ll& before = beforeDp[x][0];
both = max({both, maxBefore[x - 1], bestBefore2, bestBoth3});
before = max(before, both);
maxBefore[x] = max(maxBefore[x], before);
maxBoth[x] = max(maxBoth[x], both);
}
ll res = 0;
loop(x, N) {
for (auto [y, score] : beforeDp[x]) {
res = max(res, score);
}
for (auto [y, score] : bothDp[x]) {
res = max(res, score);
}
}
return res;
}
Compilation message
fish.cpp: In function 'long long int weightSum(int, int, int)':
fish.cpp:37:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | if (x >= fishes.size() || y2 <= y1)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
232 ms |
52868 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
38180 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
38180 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
232 ms |
52868 KB |
Possible tampering with the output |
| 2 |
Halted |
0 ms |
0 KB |
- |
