| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 635529 | marvinthang | Catfish Farm (IOI22_fish) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*************************************
* author: marvinthang *
* created: 26.08.2022 17:36:44 *
*************************************/
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define div ___div
#define left ___left
#define right ___right
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define MASK(i) (1LL << (i))
#define FULL(i) (MASK(i) - 1)
#define BIT(x, i) ((x) >> (i) & 1)
#define __builtin_popcount __builtin_popcountll
#define scan_op(...) istream & operator >> (istream &in, __VA_ARGS__ &u)
#define print_op(...) ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
template <class T> scan_op(vector <T>) { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class T> print_op(vector <T>) { out << '{'; for (size_t i = 0; i + 1 < u.size(); ++i) out << u[i] << ", "; if (!u.empty()) out << u.back(); return out << '}'; }
template <class U, class V> scan_op(pair <U, V>) { return in >> u.fi >> u.se; }
template <class U, class V> print_op(pair <U, V>) { return out << '(' << u.fi << ", " << u.se << ')'; }
template <class A, class B> inline bool minimize(A &a, B b) { A eps = 1e-9; if (a > b + eps) { a = b; return true; } return false; }
template <class A, class B> inline bool maximize(A &a, B b) { A eps = 1e-9; if (a + eps < b) { a = b; return true; } return false; }
const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {1, 0, -1, 0, 1, 1, -1, -1, 1}; // {2, 1, -2, -1, -2, 1, 2, -1, 2};
const long long oo = 1e18;
long long max_weights(int numCol, int numCatfish, vector <int> &cols, vector <int> &rows, vector <int> weights) {
vector <vector <pair <int, long long>>> atCol(numCol);
for (int i = 0; i < numCatfish; ++i)
atCol[cols[i]].push_back(make_pair(rows[i], weights[i]));
for (int i = 0; i < numCol; ++i) {
atCol[i].push_back(make_pair(numCol, 0));
sort(atCol[i].begin(), atCol[i].end());
long long pref = 0;
for (auto &[_, p]: atCol[i]) {
pref += p;
p = pref;
}
}
auto prefix_sum = [&] (int i, int x) -> long long {
assert(0 <= i && i < numCol);
auto it = lower_bound(atCol[i].begin(), atCol[i].end(), make_pair(x, -1LL));
if (it != atCol[i].begin()) return prev(it)->se;
return 0;
};
vector <vector <vector <long long>>> F(numCol, vector <vector <long long>> (2));
for (int i = 0; i < numCol; ++i) {
F[i][0].assign(atCol[i].size(), 0);
F[i][1].assign(atCol[i].size(), 0);
// cout << atCol[i] << '\n';
if (!i) continue;
// // down
long long ma = 0;
for (int cur = atCol[i].size(), pre = atCol[i - 1].size(); cur--; ) {
while (pre > 0 && atCol[i - 1][pre - 1].fi >= atCol[i][cur].fi)
--pre; maximize(ma, F[i - 1][0][pre] + prefix_sum(i, atCol[i - 1][pre].fi));
maximize(F[i][0][cur], ma - prefix_sum(i, atCol[i][cur].fi));
// cout << i << " 0 " << atCol[i][cur].fi - 1 << ' ' << F[i][0][cur] << '\n';
}
// // up
ma = i > 1 ? max(*max_element(F[i - 2][0].begin(), F[i - 2][0].end()),
*max_element(F[i - 2][1].begin(), F[i - 2][1].end())) : 0;
for (int cur = 0, pre = -1; cur < atCol[i].size(); ++cur) {
while (pre + 1 < atCol[i - 1].size() && atCol[i - 1][pre + 1].fi <= atCol[i][cur].fi)
++pre, maximize(ma, F[i - 1][1][pre] - prefix_sum(i - 1, atCol[i - 1][pre].fi));
maximize(F[i][1][cur], ma + prefix_sum(i - 1, atCol[i][cur].fi));
// cout << i << " 1 " << atCol[i][cur].fi - 1 << ' ' << F[i][1][cur] << '\n';
}
}
return max(*max_element(F[numCol - 1][0].begin(), F[numCol - 1][0].end()),
*max_element(F[numCol - 1][1].begin(), F[numCol - 1][1].end()));
}
// void process(void) {
// int n, m; cin >> n >> m;
// vector <int> x(m), y(m), w(m);
// cin >> x >> y >> w;
// cout << max_weights(n, m, x, y, w) << '\n';
// }
// int main(void) {
// ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
// file("ioi22_day1_fish");
// process();
// cerr << "Time elapsed: " << TIME << " s.\n";
// return (0^0);
// }