Submission #523847

#	Time	Username	Problem	Language	Result	Execution time	Memory
523847		amunduzbaev	Bodyguard (JOI21_bodyguard)	C++17	42 / 100	25095 ms	308992 KiB

bodyguard

#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
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 0 / 52