oj.uz

Submission #457625

# Submission time Handle Problem Language Result Execution time Memory
457625 2021-08-07T09:01:23 Z 8e7 Bodyguard (JOI21_bodyguard) C++17
7 / 100
 25000 ms 828980 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;
		for (int i = y;i < ys;i++) {
			ans = max(ans, dp[x][i] + (x ? (xv[x] - p.ff) * cost[x-1][i].ff : 0));
		}
		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 25078 ms 217248 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 415464 KB Output is correct
2 Correct 316 ms 415460 KB Output is correct
3 Correct 337 ms 409796 KB Output is correct
4 Correct 4 ms 972 KB Output is correct
5 Correct 355 ms 415452 KB Output is correct
6 Correct 308 ms 415464 KB Output is correct
7 Correct 351 ms 414764 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 415464 KB Output is correct
2 Correct 316 ms 415460 KB Output is correct
3 Correct 337 ms 409796 KB Output is correct
4 Correct 4 ms 972 KB Output is correct
5 Correct 355 ms 415452 KB Output is correct
6 Correct 308 ms 415464 KB Output is correct
7 Correct 351 ms 414764 KB Output is correct
8 Correct 539 ms 415564 KB Output is correct
9 Correct 548 ms 415568 KB Output is correct
10 Runtime error 786 ms 828980 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 317 ms 415464 KB Output is correct
2 Correct 316 ms 415460 KB Output is correct
3 Correct 337 ms 409796 KB Output is correct
4 Correct 4 ms 972 KB Output is correct
5 Correct 355 ms 415452 KB Output is correct
6 Correct 308 ms 415464 KB Output is correct
7 Correct 351 ms 414764 KB Output is correct
8 Correct 539 ms 415564 KB Output is correct
9 Correct 548 ms 415568 KB Output is correct
10 Runtime error 786 ms 828980 KB Execution killed with signal 11
11 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

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