oj.uz

Submission #419634

# Submission time Handle Problem Language Result Execution time Memory
419634 2021-06-07T10:39:28 Z amoo_safar Bodyguard (JOI21_bodyguard) C++17
42 / 100
 25000 ms 308940 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);
	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]);
		ll ans = dp[st.F][st.S];
		
		for(int j = st.F; j < nx; j++)
			ans = max(ans, dp[j][st.S] + (cy[st.S] - (P[i] - X[i])) * up[j][st.S - 1]);
		for(int j = st.S; j < ny; j++)
			ans = max(ans, dp[st.F][j] + (cx[st.F] - (P[i] + X[i])) * rt[st.F - 1][j]);
		
		// assert(cx[st.F] == P[i] + X[i]);
		// assert(cy[st.S] == P[i] - X[i]);
		cout << ans << '\n';
	}
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 303192 KB Output is correct
2 Correct 288 ms 302268 KB Output is correct
3 Correct 276 ms 306384 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 297 ms 240488 KB Output is correct
6 Correct 251 ms 209804 KB Output is correct
7 Correct 292 ms 240128 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 303192 KB Output is correct
2 Correct 288 ms 302268 KB Output is correct
3 Correct 276 ms 306384 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 297 ms 240488 KB Output is correct
6 Correct 251 ms 209804 KB Output is correct
7 Correct 292 ms 240128 KB Output is correct
8 Correct 481 ms 303044 KB Output is correct
9 Correct 494 ms 302668 KB Output is correct
10 Correct 312 ms 305600 KB Output is correct
11 Correct 11 ms 900 KB Output is correct
12 Correct 442 ms 240596 KB Output is correct
13 Correct 472 ms 209980 KB Output is correct
14 Correct 613 ms 240580 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 303192 KB Output is correct
2 Correct 288 ms 302268 KB Output is correct
3 Correct 276 ms 306384 KB Output is correct
4 Correct 3 ms 716 KB Output is correct
5 Correct 297 ms 240488 KB Output is correct
6 Correct 251 ms 209804 KB Output is correct
7 Correct 292 ms 240128 KB Output is correct
8 Correct 481 ms 303044 KB Output is correct
9 Correct 494 ms 302668 KB Output is correct
10 Correct 312 ms 305600 KB Output is correct
11 Correct 11 ms 900 KB Output is correct
12 Correct 442 ms 240596 KB Output is correct
13 Correct 472 ms 209980 KB Output is correct
14 Correct 613 ms 240580 KB Output is correct
15 Correct 2921 ms 304524 KB Output is correct
16 Correct 2928 ms 305180 KB Output is correct
17 Correct 682 ms 308940 KB Output is correct
18 Correct 93 ms 2500 KB Output is correct
19 Correct 2474 ms 242188 KB Output is correct
20 Correct 3500 ms 211756 KB Output is correct
21 Correct 4780 ms 242152 KB Output is correct

Subtask #5
0 / 53.0

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