oj.uz

Submission #523847

# Submission time Handle Problem Language Result Execution time Memory
523847 2022-02-08T09:30:50 Z amunduzbaev Bodyguard (JOI21_bodyguard) C++17
42 / 100
 25000 ms 308992 KB 
#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

const int N = 6005;
const int Q = 3e6 + 5;
const int INF = 1e10;
int a[N], t[N], t2[N], b[N], c[N];
int up[N][N], ri[N][N], dp[N][N];
int T[Q], p[Q];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	vector<int> tx, ty;
	auto add = [&](int x, int y){
		tx.push_back(x);
		ty.push_back(y);
	};
	
	int n, q; cin>>n>>q;
	vector<int> a(n), b(n), c(n), t(n), t2(n);
	for(int i=0;i<n;i++){
		cin>>t[i]>>a[i]>>b[i]>>c[i];
		t2[i] = t[i] + abs(a[i] - b[i]);
		add(t[i] + a[i], t[i] - a[i]);
		add(t2[i] + b[i], t2[i] - b[i]);
	}
	//~ for(int i=0;i<q;i++){
		//~ cin>>T[i]>>p[i];
		//~ add(T[i] + p[i], T[i] - p[i]);
	//~ }
	
	tx.push_back(INF);
	ty.push_back(INF);
	tx.push_back(-INF);
	ty.push_back(-INF);
	sort(tx.begin(), tx.end());
	tx.erase(unique(tx.begin(), tx.end()), tx.end());
	sort(ty.begin(), ty.end());
	ty.erase(unique(ty.begin(), ty.end()), ty.end());
	auto get = [&](int x, int y) -> ar<int, 2>{
		int i = lower_bound(tx.begin(), tx.end(), x) - tx.begin(), 
		j = lower_bound(ty.begin(), ty.end(), y) - ty.begin();
		return {i, j};
	};
	
	for(int i=0;i<n;i++){
		ar<int, 2> l = get(t[i] + a[i], t[i] - a[i]), 
		r = get(t2[i] + b[i], t2[i] - b[i]);
		if(l > r) swap(l, r);
		
		if(l[0] == r[0]){
			for(int j=l[1];j<r[1];j++){
				up[l[0]][j] = max(up[l[0]][j], c[i]);
			}
		} else {
			for(int j=l[0];j<r[0];j++){
				ri[j][l[1]] = max(ri[j][l[1]], c[i]);
			}
		}
	}
	
	for(int i=(int)tx.size()-2;~i;i--){
		for(int j=(int)ty.size()-2;~j;j--){
			dp[i][j] = max(dp[i+1][j] + ri[i][j] * (tx[i+1] - tx[i]),
			dp[i][j+1] + up[i][j] * (ty[j+1] - ty[j]));
		}
	}
	
	for(int i=0;i<q;i++){
		cin>>T[i]>>p[i];
		int x = T[i] + p[i], y = T[i] - p[i];
		auto n = get(x, y);
		int res = dp[n[0]][n[1]];
		for(int j=n[0];j<(int)tx.size();j++){
			res = max(res, dp[j][n[1]] + up[j][n[1]-1] * (ty[n[1]] - y));
		}
		
		for(int j=n[1];j<(int)ty.size();j++){
			res = max(res, dp[n[0]][j] + ri[n[0]-1][j] * (tx[n[0]] - x));
		}
		
		cout<<res / 2<<"\n";
	}
}

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 302784 KB Output is correct
2 Correct 254 ms 301948 KB Output is correct
3 Correct 241 ms 306056 KB Output is correct
4 Correct 3 ms 792 KB Output is correct
5 Correct 258 ms 240012 KB Output is correct
6 Correct 219 ms 209472 KB Output is correct
7 Correct 252 ms 239780 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 302784 KB Output is correct
2 Correct 254 ms 301948 KB Output is correct
3 Correct 241 ms 306056 KB Output is correct
4 Correct 3 ms 792 KB Output is correct
5 Correct 258 ms 240012 KB Output is correct
6 Correct 219 ms 209472 KB Output is correct
7 Correct 252 ms 239780 KB Output is correct
8 Correct 407 ms 302752 KB Output is correct
9 Correct 422 ms 302176 KB Output is correct
10 Correct 263 ms 305204 KB Output is correct
11 Correct 9 ms 972 KB Output is correct
12 Correct 392 ms 240264 KB Output is correct
13 Correct 417 ms 209604 KB Output is correct
14 Correct 525 ms 240196 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 302784 KB Output is correct
2 Correct 254 ms 301948 KB Output is correct
3 Correct 241 ms 306056 KB Output is correct
4 Correct 3 ms 792 KB Output is correct
5 Correct 258 ms 240012 KB Output is correct
6 Correct 219 ms 209472 KB Output is correct
7 Correct 252 ms 239780 KB Output is correct
8 Correct 407 ms 302752 KB Output is correct
9 Correct 422 ms 302176 KB Output is correct
10 Correct 263 ms 305204 KB Output is correct
11 Correct 9 ms 972 KB Output is correct
12 Correct 392 ms 240264 KB Output is correct
13 Correct 417 ms 209604 KB Output is correct
14 Correct 525 ms 240196 KB Output is correct
15 Correct 2296 ms 304828 KB Output is correct
16 Correct 2213 ms 304696 KB Output is correct
17 Correct 540 ms 308992 KB Output is correct
18 Correct 67 ms 2420 KB Output is correct
19 Correct 2063 ms 241760 KB Output is correct
20 Correct 2948 ms 211424 KB Output is correct
21 Correct 3529 ms 242028 KB Output is correct

Subtask #5
0 / 52.0

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