| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 632689 | 2022-08-20T15:53:24 Z | Olympia | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KB |
#include <bits/stdc++.h>
#include <fish.h>
using namespace std;
template<class T>
class SegmentTree {
public:
SegmentTree (int N) {
N = (1 << ((int)floor(log2(N - 1)) + 1));
this->N = N;
val.assign(2 * N, ID);
}
void update (int x, T y) {
x += N - 1;
val[x] = y;
while (x != 0) {
x = (x - 1)/2;
val[x] = merge(val[2 * x + 1], val[2 * x + 2]);
}
}
T query (int ind, const int l, const int r, int tl, int tr) {
if (tl >= l && tr <= r) {
return val[ind];
}
if (tr < l || tl > r) {
return ID;
}
return merge(query(2 * ind + 1, l, r, tl, (tl + tr)/2), query(2 * ind + 2, l, r, (tl + tr)/2 + 1, tr));
}
T query (int l, int r) {
return query(0, l, r, 0, N - 1);
}
private:
vector<T> val;
T ID = -1e17;
T merge (T x, T y) {
return max(x, y);
}
int N;
};
int64_t max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for (int i = 0; i < X.size(); i++) {
X[i]++;
}
bool all_even = true;
for (int i: X) {
if (i % 2 == 0) {
all_even = false;
}
}
if (all_even) {
int64_t w= 0;
for (int o: W) {
w += o;
}
return w;
}
int my = 0;
for (int y: Y) {
my = max(my, y);
}
my ++;
vector<pair<int,int64_t> > vec[N + 10];
map<int,int64_t> s[N + 10];
for (int i = 0; i < X.size(); i++) {
vec[X[i]].push_back(make_pair(Y[i], W[i]));
s[X[i]][Y[i]] = W[i];
}
int64_t pref[N + 10][my + 2];
for (int i = 0; i <= N + 9; i++) {
pref[i][0] = 0;
for (int j = 1; j <= my + 1; j++) {
pref[i][j] = pref[i][j - 1] + s[i][j - 1];
}
}
int64_t dp[N + 1][my + 1][3];
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= my; j++) {
for (int d = 0; d < 3; d++) {
dp[i][j][d] = -1e17;
}
}
}
dp[0][0][0] = 0;
//0 --> stagnant
//1 --> increasing
//2 --> decreasing
for (int i = 1; i <= N; i++) {
SegmentTree<int64_t> st1(my + 1);
for (int j = 0; j <= my; j++) {
st1.update(j, dp[i - 1][j][2]);
}
for (int p = 0; p <= my; p++) {
dp[i][0][0] = max(dp[i][0][0], dp[i - 1][p][0]);
}
int64_t myMax1 = -1e17;
int64_t myMax2 = dp[i - 1][0][0] - pref[i - 1][0];
for (int cur = 1; cur <= my; cur++) {
dp[i][cur][0] = max(dp[i][cur][0], max(dp[i - 1][cur][1], dp[i - 1][cur][2]));
myMax1 = max(myMax1, dp[i - 1][cur][1] - pref[i][cur] - pref[i - 1][cur]);
dp[i][cur][1] = max(dp[i][cur][1], myMax1 + pref[i + 1][cur] + pref[i - 1][cur]);
dp[i][cur][2] = max(dp[i][cur][2], st1.query(cur, my) - pref[i][cur] + pref[i + 1][cur]);
for (int d = 1; d <= 2; d++) {
myMax2 = max(myMax2, dp[i - 1][cur][0] - pref[i - 1][cur]);
dp[i][cur][d] = max(dp[i][cur][d], myMax2 + pref[i - 1][cur] + pref[i + 1][cur]);
}
}
int64_t myMax3 = -1e17;
for (int cur = my; cur >= 1; cur--) {
for (int d = 1; d <= 2; d++) {
myMax3 = max(myMax3, dp[i - 1][cur][2]);
dp[i][cur][d] = max(dp[i][cur][d], myMax3 + pref[i + 1][cur]);
}
}
}
int64_t myMax = 0;
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= my; j++) {
for (int d = 0; d <= 2; d++) {
myMax = max(myMax, dp[i][j][d]);
}
}
}
return myMax;
}