Submission #396252

#	Time	Username	Problem	Language	Result	Execution time	Memory
396252		Mlxa	Bodyguard (JOI21_bodyguard)	C++17	42 / 100	25040 ms	308612 KiB

bodyguard

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#define int ll

const int N = 9030;

// a = t + x, b = t - x

void umax(int &a, int b) {
	a = max(a, b);
}
void umin(int &a, int b) {
	a = min(a, b);
}

int n, q;
int aidx[N], bidx[N], acnt, bcnt;
int da[N][N], db[N][N], dp[N][N];
vector<tuple<int, int, int, int>> input;

int get_idx(int arr[N], int len, int val) {
	int i = (int)(lower_bound(arr, arr + len, val) - arr);
	assert(0 <= i && i < len);
	assert(arr[i] == val);
	return i;
}

signed main() {
#ifdef LC
	assert(freopen("input.txt", "r", stdin));
#endif
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> q;
	for (int t, a, b, c, i = 0; i < n; ++i) {
		cin >> t >> a >> b >> c;
		input.emplace_back(t, a, b, c);
		assert(a != b);
		assert(acnt + 3 < N && bcnt + 3 < N);
		if (a < b) {
			// t - x = const
			aidx[acnt++] = t + a;
			aidx[acnt++] = (t + abs(b - a)) + b;
			bidx[bcnt++] = t - a;
		} else {
			// t + x = const
			aidx[acnt++] = t + a;
			bidx[bcnt++] = t - a;
			bidx[bcnt++] = (t + abs(b - a)) - b;
		}
	}
	sort(aidx, aidx + acnt);
	sort(bidx, bidx + bcnt);
	acnt = (int)(unique(aidx, aidx + acnt) - aidx);
	bcnt = (int)(unique(bidx, bidx + bcnt) - bidx);
	for (auto e : input) {
		int t, a, b, c;
		tie(t, a, b, c) = e;
		assert(c % 2 == 0);
		c /= 2;
		if (a < b) {
			int j = get_idx(bidx, bcnt, t - a);
			int li = get_idx(aidx, acnt, t + a);
			int ri = get_idx(aidx, acnt, (t + abs(b - a)) + b);
			for (int i = li; i < ri; ++i) {
				umax(da[i][j], c * (aidx[i + 1] - aidx[i]));
			}
		} else {
			int i = get_idx(aidx, acnt, t + a);
			int lj = get_idx(bidx, bcnt, t - a);
			int rj = get_idx(bidx, bcnt, (t + abs(b - a)) - b);
			for (int j = lj; j < rj; ++j) {
				umax(db[i][j], c * (bidx[j + 1] - bidx[j]));
			}
		}
	}
	// cout << acnt << " " << bcnt << endl;
	// for (int i = 0; i < acnt; ++i) {
	// 	for (int j = 0; j + 1 < bcnt; ++j) {
	// 		cout << db[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }
	// cout << endl;
	// for (int i = 0; i + 1 < acnt; ++i) {
	// 	for (int j = 0; j < bcnt; ++j) {
	// 		cout << da[i][j] << " ";
	// 	}
	// 	cout << endl;
	// }
	for (int i = acnt - 1; i >= 0; --i) {
		for (int j = bcnt - 1; j >= 0; --j) {
			dp[i][j] = max(da[i][j] + dp[i + 1][j], db[i][j] + dp[i][j + 1]);
		}
	}
	for (int t, x, it = 0; it < q; ++it) {
		cin >> t >> x;
		int a = t + x, b = t - x;
		int answer = 0;
		int i = (int)(lower_bound(aidx, aidx + acnt, a) - aidx);
		int j = (int)(lower_bound(bidx, bidx + bcnt, b) - bidx);
		// cout << "ij " << i << " " << j << endl;
		// cout << "--- " << a << " " << b << endl;
		// cout << "### " << aidx[i] << " " << bidx[j] << endl;
		if (i >= acnt || j >= bcnt) {
			cout << "0\n";
			continue;
		}
		answer = dp[i][j];
		if (i) {
			for (int jj = j; jj < bcnt; ++jj) {
				assert(da[i - 1][jj] % (aidx[i] - aidx[i - 1]) == 0);
				umax(answer, dp[i][jj] + da[i - 1][jj] / (aidx[i] - aidx[i - 1]) * (aidx[i] - a));
			}
		}
		if (j) {
			for (int ii = i; ii < acnt; ++ii) {
				assert(db[ii][j - 1] % (bidx[j] - bidx[j - 1]) == 0);
				umax(answer, dp[ii][j] + db[ii][j - 1] / (bidx[j] - bidx[j - 1]) * (bidx[j] - b));
			}
		}
		cout << answer << "\n";
	}
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 53