oj.uz

Submission #419616

# Submission time Handle Problem Language Result Execution time Memory
419616 2021-06-07T10:16:00 Z amoo_safar Bodyguard (JOI21_bodyguard) C++17
27 / 100
 3160 ms 827592 KB 
// vaziat meshki-ghermeze !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
// #define int ll

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

const ll Mod = 1000000007LL;
const int N = 3 * (2802);
const int Q = 3e6 + 10;
const int Inf = 2'000'000'100;
const ll Log = 30;

// X : X + T;
// Y : X - T;

vector<ll> cx, cy;

void Add(ll x, ll y){ cx.pb(x); cy.pb(y); }
void Uni(vector<ll>& C){
	sort(all(C));
	C.resize(unique(all(C)) - C.begin());
}
void Init(){ Uni(cx); Uni(cy); }
pii Get(ll x, ll y){
	x = lower_bound(all(cx), x) - cx.begin();
	y = lower_bound(all(cy), y) - cy.begin();
	return {x, y};
}
ll T[N], T2[N], A[N], B[N], P[Q], X[Q];
ll C[N];

ll up[N][N], rt[N][N];
ll dp[N][N];

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, q;
	cin >> n >> q;
	// assert(q == 1);
	// for(int i = -3000; i <= 6000; i++) Add(i, i);

	// debug(Inf);
	for(int i = 1; i <= n; i++){
		cin >> T[i] >> A[i] >> B[i] >> C[i];
		T2[i] = abs(A[i] - B[i]) + T[i];
		C[i] /= 2;
		Add(T[i] + A[i], T[i] - A[i]);
		Add(T2[i]+ B[i],T2[i] - B[i]);
	}
	// Add(Q, Q);
	Add(Inf, Inf);
	for(int i = 1; i <= q; i++){
		cin >> P[i] >> X[i];
		Add(P[i] + X[i], P[i] - X[i]);
	}
	Init();
	for(int i = 1; i <= n; i++){
		pii st = Get(T[i] + A[i], T[i] - A[i]);
		pii fn = Get(T2[i]+ B[i],T2[i] - B[i]);
		// cerr << 
		if(st.F == fn.F){
			for(int _i = st.S; _i < fn.S; _i++)
				up[st.F][_i] = max(up[st.F][_i], C[i]);
		} else {
			
			for(int _i = st.F; _i < fn.F; _i++)
				rt[_i][st.S] = max(rt[_i][st.S], C[i]);
		}
	}
	int nx = cx.size(), ny = cy.size();
	for(int i = nx - 2; i >= 0; i--)
		for(int j = ny - 2; j >= 0; j--)
			dp[i][j] = max(1ll * up[i][j] * (cy[j + 1] - cy[j]) + dp[i][j + 1], 1ll * rt[i][j] * (cx[i + 1] - cx[i]) + dp[i + 1][j]);
	for(int i = 1; i <= q; i++){
		// if(abs(P[i] + X[i]) > 3000 || abs(P[i] - X[i]) > 3000){
		// 	cout << "0\n";
		// 	continue;
		// }
		pii st = Get(P[i] + X[i], P[i] - X[i]);
		assert(cx[st.F] == P[i] + X[i]);
		assert(cy[st.S] == P[i] - X[i]);
		cout << dp[st.F][st.S] << '\n';
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3160 ms 681296 KB Output is correct
2 Correct 3026 ms 710760 KB Output is correct
3 Correct 2853 ms 528972 KB Output is correct
4 Correct 2788 ms 462368 KB Output is correct
5 Correct 3119 ms 682188 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 303300 KB Output is correct
2 Correct 347 ms 302684 KB Output is correct
3 Correct 295 ms 306464 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 305 ms 240500 KB Output is correct
6 Correct 257 ms 209980 KB Output is correct
7 Correct 306 ms 240116 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 303300 KB Output is correct
2 Correct 347 ms 302684 KB Output is correct
3 Correct 295 ms 306464 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 305 ms 240500 KB Output is correct
6 Correct 257 ms 209980 KB Output is correct
7 Correct 306 ms 240116 KB Output is correct
8 Correct 898 ms 827592 KB Output is correct
9 Correct 811 ms 825720 KB Output is correct
10 Correct 684 ms 680928 KB Output is correct
11 Correct 59 ms 44356 KB Output is correct
12 Correct 544 ms 396964 KB Output is correct
13 Correct 697 ms 567940 KB Output is correct
14 Correct 678 ms 520876 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 303300 KB Output is correct
2 Correct 347 ms 302684 KB Output is correct
3 Correct 295 ms 306464 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 305 ms 240500 KB Output is correct
6 Correct 257 ms 209980 KB Output is correct
7 Correct 306 ms 240116 KB Output is correct
8 Correct 898 ms 827592 KB Output is correct
9 Correct 811 ms 825720 KB Output is correct
10 Correct 684 ms 680928 KB Output is correct
11 Correct 59 ms 44356 KB Output is correct
12 Correct 544 ms 396964 KB Output is correct
13 Correct 697 ms 567940 KB Output is correct
14 Correct 678 ms 520876 KB Output is correct
15 Runtime error 93 ms 27904 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 3160 ms 681296 KB Output is correct
2 Correct 3026 ms 710760 KB Output is correct
3 Correct 2853 ms 528972 KB Output is correct
4 Correct 2788 ms 462368 KB Output is correct
5 Correct 3119 ms 682188 KB Output is correct
6 Correct 330 ms 303300 KB Output is correct
7 Correct 347 ms 302684 KB Output is correct
8 Correct 295 ms 306464 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 305 ms 240500 KB Output is correct
11 Correct 257 ms 209980 KB Output is correct
12 Correct 306 ms 240116 KB Output is correct
13 Correct 898 ms 827592 KB Output is correct
14 Correct 811 ms 825720 KB Output is correct
15 Correct 684 ms 680928 KB Output is correct
16 Correct 59 ms 44356 KB Output is correct
17 Correct 544 ms 396964 KB Output is correct
18 Correct 697 ms 567940 KB Output is correct
19 Correct 678 ms 520876 KB Output is correct
20 Runtime error 93 ms 27904 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -