Submission #396258

#	Time	Username	Problem	Language	Result	Execution time	Memory
396258		Mlxa	Bodyguard (JOI21_bodyguard)	C++17	42 / 100	25107 ms	241784 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 umax(signed &a, int b) {
	a = max(a, (signed)b);
}

int n, q;
int aidx[N], bidx[N], acnt, bcnt;
signed da[N][N], db[N][N];
int 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));
	assert(freopen("output.txt", "w", stdout));
#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);
	// cout << "cnt: " << acnt << " x " << bcnt << endl;
	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);
			}
		} 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);
			}
		}
	}
	for (int i = acnt - 1; i >= 0; --i) {
		for (int j = bcnt - 1; j >= 0; --j) {
			dp[i][j] = max(	da[i][j] * (aidx[i + 1] - aidx[i]) + dp[i + 1][j],
							db[i][j] * (bidx[j + 1] - bidx[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);
		if (i >= acnt || j >= bcnt) {
			cout << "0\n";
			continue;
		}
		answer = dp[i][j];
		int u;
		if (i) {
			u = aidx[i] - a;
			for (int jj = j; jj < bcnt; ++jj) {
				umax(answer, dp[i][jj] + da[i - 1][jj] * u);
			}
		}
		if (j) {
			u = bidx[j] - b;
			for (int ii = i; ii < acnt; ++ii) {
				umax(answer, dp[ii][j] + db[ii][j - 1] * u);
			}
		}
		cout << answer << "\n";
	}
#ifdef LC
	cerr << 1000 * clock() / CLOCKS_PER_SEC << "ms" << endl;
#endif
	return 0;
}

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