제출 #529190

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
529190		blue	Bodyguard (JOI21_bodyguard)	C++17	28 / 100	3202 ms	2097156 KiB

bodyguard

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;
using vvi = vector<vi>;


const int maxN = 2'800;

int N;

vll T(1 + maxN), A(1 + maxN), B(1 + maxN), C(1 + maxN);



const int maxQ = 3'000'000;

int Q;

vll P(1 + maxQ), X(1 + maxQ);



int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> Q;
	for(int i = 1; i <= N; i++)
	{
		cin >> T[i] >> A[i] >> B[i] >> C[i];

		T[i] *= 2;
		A[i] *= 2;
		B[i] *= 2;
		C[i] /= 2;
	}

	for(int j = 1; j <= Q; j++)
	{
		cin >> P[j] >> X[j];
		P[j] *= 2;
		X[j] *= 2;
	}


	map<ll, ll> ypx_map, ymx_map;
	for(int i = 1; i <= N; i++)
	{
		ypx_map[T[i] + A[i]] = 0;
		ymx_map[T[i] - A[i]] = 0;

		ypx_map[(T[i] + abs(A[i] - B[i])) + B[i]] = 0;
		ymx_map[(T[i] + abs(A[i] - B[i])) - B[i]] = 0;
	}



//brute force start

	for(int j = 1; j <= Q; j++)
	{
		ypx_map[P[j] + X[j]] = 0;
		ymx_map[P[j] - X[j]] = 0;
	}





//brute force end




	ll pct = 0, mct = 0;

	vll ypx{-2'000'000'001LL};
	vll ymx{-2'000'000'001LL};

	for(auto& z : ypx_map) 
	{
		z.second = ++pct;
		ypx.push_back(z.first);
	}

	for(auto& z : ymx_map) 
	{
		z.second = ++mct;
		ymx.push_back(z.first);
	}

	vi start_ypx(1 + N), start_ymx(1 + N), end_ypx(1 + N), end_ymx(1 + N);
	for(int i = 1; i <= N; i++)
	{
		start_ypx[i] = ypx_map[T[i] + A[i]];
		start_ymx[i] = ymx_map[T[i] - A[i]];

		end_ypx[i] = ypx_map[T[i] + abs(A[i] - B[i]) + B[i]];
		end_ymx[i] = ymx_map[T[i] + abs(A[i] - B[i]) - B[i]];
	}




	//i = ypx, j = ymx

	vvll horiz(1 + pct, vll(1 + mct, 0)); //(i, j) -> (i, j+1)
	vvll vert(1 + pct, vll(1 + mct, 0)); //(i, j) - (i+1, j)

	for(int i = 1; i <= N; i++)
	{
		if(B[i] < A[i])
		{
			for(int j = start_ymx[i]; j < end_ymx[i]; j++)
			{
				// cerr << start_ypx[i] << " ! " << j << '\n';
				horiz[ start_ypx[i] ][j] = max(horiz[start_ypx[i]][j], (ymx[j+1] - ymx[j])/2  *  C[i]);

				// cerr << ymx[j+1] << ' ' << ymx[j] << ' ' << C[i] << '\n';

				// cerr << horiz[start_ypx[i]][j] << '\n';
			}
		}
		else
		{
			for(int j = start_ypx[i]; j < end_ypx[i]; j++)
				vert[j][ start_ymx[i] ] = max(vert[j][start_ymx[i]], (ypx[j+1] - ypx[j])/2  *  C[i]);
		}
	}



	// cerr << "\n\n\n!!!\n";

	// cerr << pct << ' ' << mct << '\n';
	// for(int i = 1; i <= N; i++)
	// {
	// 	cerr << T[i] << ' ' << A[i] << ' ' << B[i] << ' ' << C[i] << '\n';
	// }

	// for(int i = 1; i <= pct; i++)
	// {
	// 	for(int j = 1; j <= mct; j++) cerr << horiz[i][j] << ' ';
	// 		cerr << '\n';
	// }
	// cerr << "----\n";
	// for(int i = 1; i <= pct; i++)
	// {
	// 	for(int j = 1; j <= mct; j++) cerr << vert[i][j] << ' ';
	// 		cerr << '\n';
	// }




	vvll dp(1 + pct, vll(1 + mct, 0));


	for(int i = pct; i >= 1; i--)
	{
		for(int j = mct; j >= 1; j--)
		{
			if(i < pct) dp[i][j] = max(dp[i][j], dp[i+1][j] + vert[i][j]);

			if(j < mct) dp[i][j] = max(dp[i][j], dp[i][j+1] + horiz[i][j]);
		}
	}


	// for(int i = 1; i <= pct; i++)
	// {
	// 	for(int j = 1; j <= mct; j++)
	// 	{
	// 		cerr << dp[i][j] << ' ';
	// 	}
	// 	cerr << '\n';
	// }



	for(int j = 1; j <= Q; j++)
	{
		cout << dp[ ypx_map[P[j] + X[j]] ][ ymx_map[P[j] - X[j]] ] << '\n';
	}


}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 52