oj.uz

Submission #396252

# Submission time Handle Problem Language Result Execution time Memory
396252 2021-04-29T15:40:18 Z Mlxa Bodyguard (JOI21_bodyguard) C++17
42 / 100
 25000 ms 308612 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25040 ms 165388 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 303204 KB Output is correct
2 Correct 330 ms 302520 KB Output is correct
3 Correct 310 ms 306580 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 332 ms 240440 KB Output is correct
6 Correct 274 ms 209860 KB Output is correct
7 Correct 335 ms 240280 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 303204 KB Output is correct
2 Correct 330 ms 302520 KB Output is correct
3 Correct 310 ms 306580 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 332 ms 240440 KB Output is correct
6 Correct 274 ms 209860 KB Output is correct
7 Correct 335 ms 240280 KB Output is correct
8 Correct 606 ms 303164 KB Output is correct
9 Correct 596 ms 302876 KB Output is correct
10 Correct 357 ms 305760 KB Output is correct
11 Correct 38 ms 920 KB Output is correct
12 Correct 584 ms 240712 KB Output is correct
13 Correct 606 ms 210152 KB Output is correct
14 Correct 339 ms 240548 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 303204 KB Output is correct
2 Correct 330 ms 302520 KB Output is correct
3 Correct 310 ms 306580 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 332 ms 240440 KB Output is correct
6 Correct 274 ms 209860 KB Output is correct
7 Correct 335 ms 240280 KB Output is correct
8 Correct 606 ms 303164 KB Output is correct
9 Correct 596 ms 302876 KB Output is correct
10 Correct 357 ms 305760 KB Output is correct
11 Correct 38 ms 920 KB Output is correct
12 Correct 584 ms 240712 KB Output is correct
13 Correct 606 ms 210152 KB Output is correct
14 Correct 339 ms 240548 KB Output is correct
15 Correct 3820 ms 304676 KB Output is correct
16 Correct 3833 ms 304552 KB Output is correct
17 Correct 1068 ms 308612 KB Output is correct
18 Correct 150 ms 1732 KB Output is correct
19 Correct 3402 ms 241528 KB Output is correct
20 Correct 4786 ms 211096 KB Output is correct
21 Correct 348 ms 241500 KB Output is correct

Subtask #5
0 / 53.0

# Verdict Execution time Memory Grader output
1 Execution timed out 25040 ms 165388 KB Time limit exceeded
2 Halted 0 ms 0 KB -