Submission #957262

#	Time	Username	Problem	Language	Result	Execution time	Memory
957262		aaron_dcoder	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	81 ms	129784 KiB

ho_t3

#define NDEBUG


#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 1e18;

int main()
{
	ll N,L;
	cin >> N >> L;

	vector<ll> X(N+2);
	vector<ll> T(N+2);
	X[0] = 0;
	X[N+1] = L;
	for (ll i = 0; i < N; ++i)
	{
		cin >> X[i+1];
	}
	T[0] = -1;
	T[N+1] = -1;
	for (ll i = 0; i < N; ++i)
	{
		cin >> T[i+1];
	}


	// dp[ccw limit][cw limit][num] = {time_ccw, time_cw};

	vector<vector<vector<pll>>> dp(N+1,vector<vector<pll>>(N+1,vector<pll>(N+1,{INFTY,INFTY})));

	dp[0][0][0]={0,0};
	for (ll ns=1;ns<=N; ++ns)
	{
		dp[0][0][ns] = {INFTY,INFTY};
	}

	for (ll ccw = 0; ccw <= N; ++ccw)
	{
		for (ll cw = 0; cw <= N; ++cw)
		{
			if (cw+ccw>=N) continue;
			dbgv(ccw << " " << cw);

			for (ll ns = 0; ns < N; ++ns)
			{
				//dbgv(ns);
				// cw entend
				if (dp[ccw][cw][ns].e1<INFTY)
				{
					
					bool cancollect = T[cw]>=dp[ccw][cw][ns].e1;
					//assert(!cancollect);
				
					dp[ccw][cw+1][ns+cancollect].e1 = min(dp[ccw][cw+1][ns+cancollect].e1, (X[cw+1]-X[cw]) + dp[ccw][cw][ns].e1);

					dp[ccw+1][cw][ns+cancollect].e0 = min(dp[ccw+1][cw][ns+cancollect].e0, X[cw]+(L-X[N+1-(ccw+1)]) + dp[ccw][cw][ns].e1);

				}
				//dbgv(ns);

				// ccw extend
				if (dp[ccw][cw][ns].e0 < INFTY)
				{
					bool cancollect = T[N+1-ccw]>=dp[ccw][cw][ns].e0;
						//				assert(!cancollect);


					dp[ccw+1][cw][ns+cancollect].e0 = min(dp[ccw+1][cw][ns+cancollect].e0, (X[N+1-ccw]-X[N+1-(ccw+1)])+dp[ccw][cw][ns].e0);
					//dbg('j');
					dp[ccw][cw+1][ns+cancollect].e1 = min(dp[ccw][cw+1][ns+cancollect].e1, X[cw+1]+(L-X[N+1-(ccw)]) + dp[ccw][cw][ns].e0);
				}
			}
		}
	}


	ll outp=0;
	for (ll ccw = 0; ccw <= N; ++ccw)
	{
		for (ll cw = 0; cw <= N; ++cw)
		{
			if (cw+ccw>N) continue;
			for (ll ns = 0; ns <= N; ++ns)
			{
									dbgv(ns);
					dbg( ccw << " " << cw << " ");

				if (dp[ccw][cw][ns].e1<INFTY)
				{
					bool cancollect = T[cw]>=dp[ccw][cw][ns].e1;
					outp = max(outp,ns+cancollect);
				}
				if (dp[ccw][cw][ns].e0 < INFTY)
				{
					bool cancollect = T[N+1-ccw]>=dp[ccw][cw][ns].e0;
					outp = max(outp,ns+cancollect);
				}
			}
		}
	}
	dbgv('h');
	dbgfor (pll a : dp[1][0]) cerr << a.e0 << "," << a.e1 << "\n";

	cout << outp;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75