| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1182993 | Swan | Catfish Farm (IOI22_fish) | C++20 | 0 ms | 0 KiB |
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <climits>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
#include <optional>
//#define int long long
#define INP freopen("subrev.in","r",stdin)
#define OUTP freopen("subrev.out","w",stdout)
using ld = long double;
using LD = ld;
using namespace std;
const int maxn = 3e5 + 123;
struct st {
int y = 0;
long long val = 0;
long long pointsBelow = 0;
st() {}
st (int y, long long val, int pointsBelow) : y(y), val(val), pointsBelow(pointsBelow) {}
bool operator< (const st& ot) const {
return y < ot.y;
}
bool operator< (const int val) const {
return y < val;
}
friend bool operator<(const int& val, const st& ot) {
return val < ot.y;
}
};
vector<st> points[maxn];
vector<long long> prefSum[maxn];
long long getSum(int col, int y) {
if (col < 0) return 0;
long long ans = 0;
int num = upper_bound(points[col].begin(), points[col].end(), y) - points[col].begin();
if (num == points[col].size()) num--;
if (num == -1) {
return 0;
}
return prefSum[col][num];
}
long long solve(vector<st>& prevRise, vector<st>& prevDown, vector<st>& prevNoPiles, vector<st>& curRise, vector<st>& curDown, vector<st>& curNoPiles, vector<int>& interestingPoints, int curx) {
int prevDownPointer = -1;
int prevRisePointer = -1;
int prevNoPilesPointer = -1;
long long bestDown = 0;
long long bestRise = 0;
long long bestNoPiles = 0;
long long bestNoPilesHigher = 0;
long long overallMax = 0;
for (auto a : prevNoPiles) bestNoPilesHigher = max(bestNoPilesHigher, a.val);
for (int i = 0; i < interestingPoints.size(); i++) {
while (prevRisePointer + 1 < prevRise.size() && prevRise[prevRisePointer + 1].y < interestingPoints[i]) {
prevRisePointer++;
bestDown = max(bestDown, prevRise[prevRisePointer].val - prevRise[prevRisePointer].pointsBelow);
}
while (prevNoPilesPointer + 1 < prevNoPiles.size() && prevNoPiles[prevNoPilesPointer + 1].y < interestingPoints[i]) {
prevNoPilesPointer++;
bestNoPiles = max(bestNoPiles, prevNoPiles[prevNoPilesPointer].val - prevNoPiles[prevNoPilesPointer].pointsBelow);
}
long long numberOfPoints = 0;
long long numberOfPointsNow = 0;
if (curx) {
numberOfPoints = getSum(curx - 1, interestingPoints[i]);
}
numberOfPointsNow = getSum(curx, interestingPoints[i] + 1);
long long ans = bestNoPilesHigher;
ans = max(ans, numberOfPoints + max(bestDown, bestNoPiles));
curRise.push_back({interestingPoints[i], ans , numberOfPointsNow});
}
prevDownPointer = prevDown.size();
prevRisePointer = prevRise.size();
bestDown = 0;
bestRise = 0;
bestNoPiles = 0;
for (int i = interestingPoints.size() - 1; i >= 0; i--) {
while (prevRisePointer - 1 >= 0 && prevRise[prevRisePointer - 1].y > interestingPoints[i]) {
prevRisePointer--;
long long numberOfPointsNowSum = getSum(curx, prevRise[prevRisePointer - 1].y);
bestRise = max(bestRise, prevRise[prevRisePointer].val + numberOfPointsNowSum);
bestNoPiles = max(bestNoPiles, prevRise[prevRisePointer].val);
}
while (prevDownPointer - 1 >= 0 && prevDown[prevDownPointer - 1].y > interestingPoints[i]) {
prevDownPointer--;
long long numberOfPointsNowSum = getSum(curx, prevDown[prevDownPointer - 1].y);
bestDown = max(bestDown, prevDown[prevDownPointer].val + numberOfPointsNowSum);
bestNoPiles = max(bestNoPiles, prevDown[prevDownPointer].val);
}
long long numberOfPointsNow = getSum(curx, interestingPoints[i] + 1);
long long ans = max(bestDown, bestRise) - numberOfPointsNow;
curDown.push_back({interestingPoints[i], ans , numberOfPointsNow});
if (prevDownPointer == prevDown.size() && prevRisePointer == prevRise.size()) ans = 0;
else ans = bestNoPiles + numberOfPointsNow;
curNoPiles.push_back({interestingPoints[i], ans, numberOfPointsNow});
}
reverse(curDown.begin(), curDown.end());
for (auto a : prevDown) overallMax = max(overallMax, a.val);
for (auto a : prevRise) overallMax = max(overallMax, a.val);
for (auto a : prevNoPiles) overallMax = max(overallMax, a.val);
curNoPiles.push_back({-1, overallMax, 0});
reverse(curNoPiles.begin(), curNoPiles.end());
return overallMax;
}
long long max_weights(int N, int M, const vector<int>& X, const vector<int>& Y, const vector<int>& W) {
for (int i = 0; i < M; i++) {
points[X[i]].push_back(st({Y[i], W[i], 0}));
}
for (int i = 0; i < N; i++) {
sort(points[i].begin(), points[i].end());
for (int j = 0; j < points[i].size(); j++) {
points[i][j].pointsBelow = j;
prefSum[i].push_back(points[i][j].val);
if (j) prefSum[i][j] += prefSum[i][j - 1];
}
}
vector<st> prevRise;
vector<st> prevDown;
vector<st> prevNoPiles;
vector<st> curRise;
vector<st> curDown;
vector<st> curNoPiles;
long long ans = 0;
curNoPiles.push_back({-1, 0, 0});
for (int i = 0; i < N; i++) {
swap(prevRise, curRise);
swap(prevDown, curDown);
swap(prevNoPiles, curNoPiles);
curRise.clear();
curDown.clear();
curNoPiles.clear();
vector<int> interestingPointsUnsorted;
vector<int> interestingPoints;
if (i) {
for (auto a : points[i - 1]) interestingPointsUnsorted.push_back(a.y);
}
if (i + 1 < N) {
for (auto a : points[i + 1]) interestingPointsUnsorted.push_back(a.y);
}
sort(interestingPointsUnsorted.begin(), interestingPointsUnsorted.end());
for (int i = 0; i < interestingPointsUnsorted.size(); i++) {
if (i == interestingPointsUnsorted.size() - 1) {
if (i && interestingPointsUnsorted[i] != interestingPointsUnsorted[i - 1]) {
interestingPoints.push_back(interestingPointsUnsorted[i]);
}
}
if (interestingPointsUnsorted[i] != interestingPointsUnsorted[i + 1]) {
interestingPoints.push_back(interestingPointsUnsorted[i]);
}
}
ans = max(ans, solve(prevRise, prevDown, prevNoPiles, curRise, curDown, curNoPiles, interestingPoints, i));
}
for (auto a : curDown) ans = max(ans, a.val);
for (auto a : curRise) ans = max(ans, a.val);
for (auto a : curNoPiles) ans = max(ans, a.val);
return ans;
}