oj.uz

Submission #529195

# Submission time Handle Problem Language Result Execution time Memory
529195 2022-02-22T11:35:11 Z blue Bodyguard (JOI21_bodyguard) C++17
42 / 100
 25000 ms 741216 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;
	}

	ll pct = 0, mct = 0;

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

	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)

	vvll horiz_basic(1 + pct, vll(1 + mct, 0)); //(i, j) -> (i, j+1)
	vvll vert_basic(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_basic[ start_ypx[i] ][j] = max(horiz_basic[ start_ypx[i] ][j], C[i]);
				// horiz[ start_ypx[i] ][j] = max(horiz[start_ypx[i]][j], (ymx[j+1] - ymx[j])/2  *  C[i]);
				horiz[start_ypx[i]][j] = horiz_basic[start_ypx[i]][j] * (ymx[j+1] - ymx[j]) / 2;

				// 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_basic[j][ start_ymx[i] ] = max(vert_basic[j][start_ymx[i]], C[i]);
				vert[j][ start_ymx[i] ] = (ypx[j+1] - ypx[j])/2  *  vert_basic[ j ][ start_ymx[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++)
	{
		ll res = 0;

		if(P[j] + X[j] <= ypx.back())
		{
			if(P[j] - X[j] <= ymx.back())
			{
				int pi = 0, mi = 0;
				while(ypx[pi] < P[j] + X[j])
					pi++;

				while(ymx[mi] < P[j] - X[j])
					mi++;

				for(int pi2 = pi; pi2 <= pct; pi2++)
				{
					res = max(res, dp[pi2][mi] + (ymx[mi] - (P[j] - X[j]))/2 * horiz_basic[pi2][mi - 1]);
				}

				for(int mi2 = mi; mi2 <= mct; mi2++)
				{
					res = max(res, dp[pi][mi2] + (ypx[pi] - (P[j] + X[j]))/2 * vert_basic[pi - 1][mi2]);
				}
			}
		}

		cout << res << '\n';
	}


}

Subtask #1
0 / 6.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 739636 KB Output is correct
2 Correct 466 ms 739728 KB Output is correct
3 Correct 409 ms 730076 KB Output is correct
4 Correct 22 ms 48160 KB Output is correct
5 Correct 487 ms 739520 KB Output is correct
6 Correct 454 ms 739524 KB Output is correct
7 Correct 501 ms 738708 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 739636 KB Output is correct
2 Correct 466 ms 739728 KB Output is correct
3 Correct 409 ms 730076 KB Output is correct
4 Correct 22 ms 48160 KB Output is correct
5 Correct 487 ms 739520 KB Output is correct
6 Correct 454 ms 739524 KB Output is correct
7 Correct 501 ms 738708 KB Output is correct
8 Correct 606 ms 739788 KB Output is correct
9 Correct 621 ms 739780 KB Output is correct
10 Correct 436 ms 728828 KB Output is correct
11 Correct 28 ms 48204 KB Output is correct
12 Correct 634 ms 739532 KB Output is correct
13 Correct 675 ms 739608 KB Output is correct
14 Correct 754 ms 739596 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 739636 KB Output is correct
2 Correct 466 ms 739728 KB Output is correct
3 Correct 409 ms 730076 KB Output is correct
4 Correct 22 ms 48160 KB Output is correct
5 Correct 487 ms 739520 KB Output is correct
6 Correct 454 ms 739524 KB Output is correct
7 Correct 501 ms 738708 KB Output is correct
8 Correct 606 ms 739788 KB Output is correct
9 Correct 621 ms 739780 KB Output is correct
10 Correct 436 ms 728828 KB Output is correct
11 Correct 28 ms 48204 KB Output is correct
12 Correct 634 ms 739532 KB Output is correct
13 Correct 675 ms 739608 KB Output is correct
14 Correct 754 ms 739596 KB Output is correct
15 Correct 2669 ms 741056 KB Output is correct
16 Correct 2615 ms 741216 KB Output is correct
17 Correct 809 ms 732316 KB Output is correct
18 Correct 57 ms 49092 KB Output is correct
19 Correct 2265 ms 740500 KB Output is correct
20 Correct 3041 ms 740704 KB Output is correct
21 Correct 3686 ms 740516 KB Output is correct

Subtask #5
0 / 52.0

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