oj.uz

Submission #457631

# Submission time Handle Problem Language Result Execution time Memory
457631 2021-08-07T09:05:34 Z 8e7 Bodyguard (JOI21_bodyguard) C++17
42 / 100
 25000 ms 417268 KB 
//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <cmath>
#include <queue>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 3005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
struct seg{
	pii st, ed;
	ll cost;
	seg(){st = {0, 0}, ed = {0, 0}, cost = 0;}
	seg(pii x, pii y, ll c){st = x, ed = y, cost = c;};
} arr[maxn];
vector<ll> xv, yv;
vector<vector<pii> > cost;
vector<vector<ll> > dp;
int main() {
	io
	int n, q;
	cin >> n >> q;
	auto turn = [&](pii p) {return make_pair((p.ff - p.ss), (p.ff + p.ss));};
	for (int i = 0;i < n;i++) {
		ll t, a, b, c;
		cin >> t >> a >> b >> c;
		pii p1 = {t, a}, p2 = {t + abs(b - a), b};
		p1 = turn(p1), p2 = turn(p2);
		arr[i] = seg(p1, p2, c / 2);
		xv.push_back(p1.ff), xv.push_back(p2.ff);
		yv.push_back(p1.ss), yv.push_back(p2.ss);
	}
	sort(xv.begin(), xv.end()), sort(yv.begin(), yv.end());
	xv.resize(int(unique(xv.begin(), xv.end()) - xv.begin()));
	yv.resize(int(unique(yv.begin(), yv.end()) - yv.begin()));	
	//pary(xv.begin(), xv.end());
	//pary(yv.begin(), yv.end());
	int xs = xv.size(), ys = yv.size();
	for (int i = 0;i < xs;i++) {
		vector<pii> ac(ys, {0, 0});
		vector<ll> dc(ys, 0);
		cost.push_back(ac), dp.push_back(dc);
	}
	for (int i = 0;i < n;i++) {
		int sx = lower_bound(xv.begin(), xv.end(), arr[i].st.ff) - xv.begin();
		int tx = lower_bound(xv.begin(), xv.end(), arr[i].ed.ff) - xv.begin();
		int sy = lower_bound(yv.begin(), yv.end(), arr[i].st.ss) - yv.begin();
		int ty = lower_bound(yv.begin(), yv.end(), arr[i].ed.ss) - yv.begin();
		if (sx == tx) {
			for (int j = sy;j < ty;j++) cost[sx][j].ss = max(cost[sx][j].ss, arr[i].cost);	
		} else {
			for (int j = sx;j < tx;j++) cost[j][sy].ff = max(cost[j][sy].ff, arr[i].cost);	
		}
	}
	for (int i = xs - 1;i >= 0;i--) {
		for (int j = ys - 1;j >= 0;j--) {
			dp[i][j] = max((i < xs - 1 ? dp[i + 1][j] + (xv[i + 1] - xv[i]) * cost[i][j].ff : 0), 
					(j < ys - 1 ? dp[i][j + 1] + (yv[j + 1] - yv[j]) * cost[i][j].ss : 0));
		}
	}
	
	while (q--) {
		pii p;
		cin >> p.ff >> p.ss;
		p = turn(p);
		int x = lower_bound(xv.begin(), xv.end(), p.ff) - xv.begin();
		int y = lower_bound(yv.begin(), yv.end(), p.ss) - yv.begin();
		//debug(x, y);
		ll ans = 0;
		if (x < xs) {
			for (int i = y;i < ys;i++) {
				ans = max(ans, dp[x][i] + (x ? (xv[x] - p.ff) * cost[x-1][i].ff : 0));
			}
		}
		if (y < ys) {
			for (int i = x;i < xs;i++) {
				ans = max(ans, dp[i][y] + (y ? (yv[y] - p.ss) * cost[i][y-1].ss : 0));
			}
		}	
		cout << ans << "\n";
		//debug();
	}
}
/*

2 2
1 2 1 4
3 1 3 2
1 2
3 3




*/

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 415380 KB Output is correct
2 Correct 327 ms 415412 KB Output is correct
3 Correct 318 ms 409720 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 344 ms 415284 KB Output is correct
6 Correct 323 ms 415428 KB Output is correct
7 Correct 355 ms 414760 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 415380 KB Output is correct
2 Correct 327 ms 415412 KB Output is correct
3 Correct 318 ms 409720 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 344 ms 415284 KB Output is correct
6 Correct 323 ms 415428 KB Output is correct
7 Correct 355 ms 414760 KB Output is correct
8 Correct 560 ms 415432 KB Output is correct
9 Correct 581 ms 415332 KB Output is correct
10 Correct 475 ms 409024 KB Output is correct
11 Correct 13 ms 1100 KB Output is correct
12 Correct 569 ms 415632 KB Output is correct
13 Correct 569 ms 415500 KB Output is correct
14 Correct 559 ms 415500 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 323 ms 415380 KB Output is correct
2 Correct 327 ms 415412 KB Output is correct
3 Correct 318 ms 409720 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 344 ms 415284 KB Output is correct
6 Correct 323 ms 415428 KB Output is correct
7 Correct 355 ms 414760 KB Output is correct
8 Correct 560 ms 415432 KB Output is correct
9 Correct 581 ms 415332 KB Output is correct
10 Correct 475 ms 409024 KB Output is correct
11 Correct 13 ms 1100 KB Output is correct
12 Correct 569 ms 415632 KB Output is correct
13 Correct 569 ms 415500 KB Output is correct
14 Correct 559 ms 415500 KB Output is correct
15 Correct 3054 ms 417144 KB Output is correct
16 Correct 3130 ms 417268 KB Output is correct
17 Correct 2207 ms 411624 KB Output is correct
18 Correct 52 ms 1988 KB Output is correct
19 Correct 3332 ms 416604 KB Output is correct
20 Correct 3744 ms 416624 KB Output is correct
21 Correct 2842 ms 416388 KB Output is correct

Subtask #5
0 / 52.0

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