oj.uz

Submission #529190

# Submission time Handle Problem Language Result Execution time Memory
529190 2022-02-22T11:20:14 Z blue Bodyguard (JOI21_bodyguard) C++17
28 / 100
 3202 ms 2097156 KB 
#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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3159 ms 1028328 KB Output is correct
2 Correct 3042 ms 1024844 KB Output is correct
3 Correct 2922 ms 951976 KB Output is correct
4 Correct 2920 ms 943008 KB Output is correct
5 Correct 3202 ms 1324004 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 463308 KB Output is correct
2 Correct 352 ms 463208 KB Output is correct
3 Correct 326 ms 457588 KB Output is correct
4 Correct 22 ms 48072 KB Output is correct
5 Correct 386 ms 463268 KB Output is correct
6 Correct 395 ms 463280 KB Output is correct
7 Correct 371 ms 462460 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 463308 KB Output is correct
2 Correct 352 ms 463208 KB Output is correct
3 Correct 326 ms 457588 KB Output is correct
4 Correct 22 ms 48072 KB Output is correct
5 Correct 386 ms 463268 KB Output is correct
6 Correct 395 ms 463280 KB Output is correct
7 Correct 371 ms 462460 KB Output is correct
8 Correct 921 ms 1267136 KB Output is correct
9 Correct 912 ms 1267392 KB Output is correct
10 Correct 870 ms 1260400 KB Output is correct
11 Correct 99 ms 142684 KB Output is correct
12 Correct 663 ms 759800 KB Output is correct
13 Correct 906 ms 1267032 KB Output is correct
14 Correct 885 ms 1267096 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 463308 KB Output is correct
2 Correct 352 ms 463208 KB Output is correct
3 Correct 326 ms 457588 KB Output is correct
4 Correct 22 ms 48072 KB Output is correct
5 Correct 386 ms 463268 KB Output is correct
6 Correct 395 ms 463280 KB Output is correct
7 Correct 371 ms 462460 KB Output is correct
8 Correct 921 ms 1267136 KB Output is correct
9 Correct 912 ms 1267392 KB Output is correct
10 Correct 870 ms 1260400 KB Output is correct
11 Correct 99 ms 142684 KB Output is correct
12 Correct 663 ms 759800 KB Output is correct
13 Correct 906 ms 1267032 KB Output is correct
14 Correct 885 ms 1267096 KB Output is correct
15 Runtime error 1032 ms 2097156 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #5
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3159 ms 1028328 KB Output is correct
2 Correct 3042 ms 1024844 KB Output is correct
3 Correct 2922 ms 951976 KB Output is correct
4 Correct 2920 ms 943008 KB Output is correct
5 Correct 3202 ms 1324004 KB Output is correct
6 Correct 353 ms 463308 KB Output is correct
7 Correct 352 ms 463208 KB Output is correct
8 Correct 326 ms 457588 KB Output is correct
9 Correct 22 ms 48072 KB Output is correct
10 Correct 386 ms 463268 KB Output is correct
11 Correct 395 ms 463280 KB Output is correct
12 Correct 371 ms 462460 KB Output is correct
13 Correct 921 ms 1267136 KB Output is correct
14 Correct 912 ms 1267392 KB Output is correct
15 Correct 870 ms 1260400 KB Output is correct
16 Correct 99 ms 142684 KB Output is correct
17 Correct 663 ms 759800 KB Output is correct
18 Correct 906 ms 1267032 KB Output is correct
19 Correct 885 ms 1267096 KB Output is correct
20 Runtime error 1032 ms 2097156 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -