Submission #799032

#	Time	Username	Problem	Language	Result	Execution time	Memory
799032		MadokaMagicaFan	Catfish Farm (IOI22_fish)	C++17	100 / 100	222 ms	25424 KiB

fish

#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define sz(v)	((int) v.size())

const int N = 1e5;

int dp1[N+5], dp2[N+5];

struct aint {
	int n;
	vector<ll> f;

	aint (int _n) {
		n = _n;
		f.assign(n<<1, 0);
	}

	ll query(int l, int r) {
		l += n; r += n+1;
		ll res = 0;
		for (;l < r; l>>=1, r>>=1) {
			if (l&1) res = max(res, f[l++]);
			if (r&1) res = max(res, f[--r]);
		}
		return res;
	}

	void upd(int x, ll v) {
		x += n;
		for (f[x] = max(f[x], v); x > 1; x>>=1) {
			f[x>>1] = max(f[x], f[x^1]);
		}
	}
};
ll mv1[N+5], mv2[N+5];

ll
max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w)
{
	vector<array<int, 3>> u(m), d(m);

	for (int i = 0; i < m; ++i) {
		u[i] = {x[i], y[i], i};
		d[i] = {x[i], -y[i], i};
	}

	sort(u.begin(), u.end());
	sort(d.begin(), d.end());
	reverse(u.begin(), u.end());
	reverse(d.begin(), d.end());

	int up, dp;
	up = dp = 0;
	aint t1(n+5), t2(n+5);
	ll t, v, i;

	for (int x = n-1; x >= 0; --x) {
		while (up < sz(u) && u[up][0] == x) {
			if (x < n-1) {
				i = u[up][2];
				v = w[i];
				t = t1.query(y[i]+1, n+2);
				t = max({t, mv2[x+2], mv1[x+3]});
				t1.upd(y[i], t+v);
			}
			++up;
		}

		while (dp < sz(d) && d[dp][0] == x) {
			if (x > 0) {
				i = d[dp][2];
				v = w[i]; t = 0;
				if (y[i])
					t = t2.query(0, y[i]-1);

				t = max({t, mv1[x+1], mv2[x+2]}) + v;
				t2.upd(y[i], t);
			}
			++dp;
		}

		mv1[x] = mv1[x+1];
		mv2[x] = mv2[x+1];

		mv1[x] =t1.query(0, n+1);
		mv2[x] =t2.query(0, n+1);
	}

	return max(t1.query(0, n+1), t2.query(0, n+1));
}

• Subtask 1: 3 / 3
• Subtask 2: 6 / 6
• Subtask 3: 9 / 9
• Subtask 4: 14 / 14
• Subtask 5: 21 / 21
• Subtask 6: 17 / 17
• Subtask 7: 14 / 14
• Subtask 8: 16 / 16