This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h> //uh may be changing style make it better ?
#ifndef LOCAL
#include <fish.h>
#endif // LOCAL
using namespace std;
#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
template<typename T> bool maximize(T& a, const T& b){
if(a < b) return a = b, true; return false;
}
long long max_weights(int sizeBoard, int nFishes, vector<int> column, vector<int> row, vector<int> weight){
vector<vector<pair<int, int>>> fishes(sizeBoard);
for(int i = 0; i < nFishes; ++i){
fishes[column[i]].emplace_back(row[i], weight[i]);
}
vector<vector<long long>> pref(sizeBoard);
vector<vector<long long>> up(sizeBoard), down(sizeBoard);
for(int i = 0; i < sizeBoard; ++i){
fishes[i].emplace_back(sizeBoard, 0);
sort(all(fishes[i]));
pref[i].resize(sz(fishes[i]));
for(int j = 0; j < sz(fishes[i]); ++j){
pref[i][j] = (j > 0 ? pref[i][j - 1] : 0) + fishes[i][j].second;
}
up[i].resize(sz(fishes[i]));
down[i].resize(sz(fishes[i]));
}
auto prefixSum = [&](int c, int pos) -> long long{
int l = 0, r = sz(fishes[c]) - 1;
long long sum = 0;
assert(!fishes[c].empty());
while(l <= r){
int mid = l + r >> 1;
if(fishes[c][mid].first < pos) sum = pref[c][mid], l = mid + 1;
else r = mid - 1;
}
return sum;
};
auto maxAll = [&](int col) -> long long{
return max(*max_element(all(up[col])), *max_element(all(down[col])));
};
//let h[i] be the height of the chosen pier at column i
for(int i = 1; i < sizeBoard; ++i){
//calculate the down[i] (case h[i - 1] > h[i])
long long mx = 0;
for(int j = sz(fishes[i]) - 1, ptr = sz(fishes[i - 1]) - 1; j >= 0; --j){
while(ptr >= 0 && fishes[i - 1][ptr].first >= fishes[i][j].first){
maximize(mx, max(up[i - 1][ptr], down[i - 1][ptr]) + prefixSum(i, fishes[i - 1][ptr].first));
--ptr;
}
maximize(down[i][j], mx - prefixSum(i, fishes[i][j].first));
}
//consider h[i - 1] < h[i] and case h[i - 2] > h[i - 1] < h[i]
mx = (i > 1 ? maxAll(i - 2) : 0);
for(int j = 0, ptr = 0; j < sz(fishes[i]); ++j){
while(ptr < sz(fishes[i - 1]) && fishes[i - 1][ptr].first <= fishes[i][j].first){
maximize(mx, up[i - 1][ptr] - prefixSum(i - 1, fishes[i - 1][ptr].first));
++ptr;
}
maximize(up[i][j], mx + prefixSum(i - 1, fishes[i][j].first));
}
}
long long ans = 0;
for(int i = 0; i < sizeBoard; ++i){
for(int j = 0; j < sz(fishes[i]); ++j){
// assert(j < sz(up[i]));
// assert(j < sz(down[i]));
// cout << "(" << i << ", " << fishes[i][j].first << ") = " << up[i][j] << ' ' << down[i][j] << '\n';
maximize(ans, max(up[i][j], down[i][j]));
}
}
return ans;
}
#ifdef LOCAL
int main(){
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
int n, m;
cin >> n >> m;
vector<int> x(m), y(m), z(m);
for(int i = 0; i < m; ++i) cin >> x[i] >> y[i] >> z[i];
cout << max_weights(n, m, x, y, z) << '\n';
return 0;
}
#endif // LOCAL
Compilation message (stderr)
fish.cpp: In function 'bool maximize(T&, const T&)':
fish.cpp:12:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
12 | if(a < b) return a = b, true; return false;
| ^~
fish.cpp:12:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
12 | if(a < b) return a = b, true; return false;
| ^~~~~~
fish.cpp: In lambda function:
fish.cpp:40:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | int mid = l + r >> 1;
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |