oj.uz

Submission #419631

# Submission time Handle Problem Language Result Execution time Memory
419631 2021-06-07T10:37:46 Z amoo_safar Bodyguard (JOI21_bodyguard) C++17
22 / 100
 25000 ms 827968 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 25101 ms 642084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 303300 KB Output is correct
2 Correct 306 ms 302444 KB Output is correct
3 Correct 272 ms 306428 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 298 ms 240620 KB Output is correct
6 Correct 241 ms 209876 KB Output is correct
7 Correct 284 ms 240064 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 303300 KB Output is correct
2 Correct 306 ms 302444 KB Output is correct
3 Correct 272 ms 306428 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 298 ms 240620 KB Output is correct
6 Correct 241 ms 209876 KB Output is correct
7 Correct 284 ms 240064 KB Output is correct
8 Correct 1207 ms 827968 KB Output is correct
9 Correct 1195 ms 825676 KB Output is correct
10 Correct 875 ms 680904 KB Output is correct
11 Correct 117 ms 44244 KB Output is correct
12 Correct 802 ms 397364 KB Output is correct
13 Correct 1131 ms 568428 KB Output is correct
14 Correct 1143 ms 521088 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 303300 KB Output is correct
2 Correct 306 ms 302444 KB Output is correct
3 Correct 272 ms 306428 KB Output is correct
4 Correct 3 ms 844 KB Output is correct
5 Correct 298 ms 240620 KB Output is correct
6 Correct 241 ms 209876 KB Output is correct
7 Correct 284 ms 240064 KB Output is correct
8 Correct 1207 ms 827968 KB Output is correct
9 Correct 1195 ms 825676 KB Output is correct
10 Correct 875 ms 680904 KB Output is correct
11 Correct 117 ms 44244 KB Output is correct
12 Correct 802 ms 397364 KB Output is correct
13 Correct 1131 ms 568428 KB Output is correct
14 Correct 1143 ms 521088 KB Output is correct
15 Runtime error 90 ms 26992 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #5
0 / 53.0

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