oj.uz

Submission #396258

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

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 240672 KB Output is correct
2 Correct 263 ms 240152 KB Output is correct
3 Correct 242 ms 240196 KB Output is correct
4 Correct 3 ms 720 KB Output is correct
5 Correct 266 ms 209312 KB Output is correct
6 Correct 228 ms 193988 KB Output is correct
7 Correct 272 ms 209148 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 240672 KB Output is correct
2 Correct 263 ms 240152 KB Output is correct
3 Correct 242 ms 240196 KB Output is correct
4 Correct 3 ms 720 KB Output is correct
5 Correct 266 ms 209312 KB Output is correct
6 Correct 228 ms 193988 KB Output is correct
7 Correct 272 ms 209148 KB Output is correct
8 Correct 476 ms 240648 KB Output is correct
9 Correct 472 ms 240340 KB Output is correct
10 Correct 287 ms 239940 KB Output is correct
11 Correct 9 ms 716 KB Output is correct
12 Correct 445 ms 209260 KB Output is correct
13 Correct 496 ms 194048 KB Output is correct
14 Correct 273 ms 209308 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 240672 KB Output is correct
2 Correct 263 ms 240152 KB Output is correct
3 Correct 242 ms 240196 KB Output is correct
4 Correct 3 ms 720 KB Output is correct
5 Correct 266 ms 209312 KB Output is correct
6 Correct 228 ms 193988 KB Output is correct
7 Correct 272 ms 209148 KB Output is correct
8 Correct 476 ms 240648 KB Output is correct
9 Correct 472 ms 240340 KB Output is correct
10 Correct 287 ms 239940 KB Output is correct
11 Correct 9 ms 716 KB Output is correct
12 Correct 445 ms 209260 KB Output is correct
13 Correct 496 ms 194048 KB Output is correct
14 Correct 273 ms 209308 KB Output is correct
15 Correct 3179 ms 241784 KB Output is correct
16 Correct 3160 ms 241412 KB Output is correct
17 Correct 647 ms 241428 KB Output is correct
18 Correct 37 ms 972 KB Output is correct
19 Correct 2666 ms 209816 KB Output is correct
20 Correct 3852 ms 194556 KB Output is correct
21 Correct 282 ms 209860 KB Output is correct

Subtask #5
0 / 53.0

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