Submission #967422

#	Time	Username	Problem	Language	Result	Execution time	Memory
967422		penguin133	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	1473 ms	151816 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
#define t4 tuple <int, int, int, int>
int n, l, X[205], T[205], dist[205][205][205][2];

void solve(){
	cin >> n >> l;
	for(int i = 1; i <= n; i++)cin >> X[i];
	for(int i = 1; i <= n; i++)cin >> T[i];
	for(int i = 0; i <= n; i++)for(int j = 0; j <= n; j++)for(int k = 0; k <= n; k++)dist[i][j][k][0] = dist[i][j][k][1] = 1e18;
	priority_queue <pair <int, t4> , vector <pair <int, t4> >, greater <pair <int, t4> > > pq;
	pq.push({X[1], {2, n, (T[1] >= X[1]), 0}});
	dist[2][n][T[1] >= X[1]][0] = X[1];
	pq.push({l - X[n], {1, n - 1, (T[n] >= l - X[n]), 1}});
	dist[1][n - 1][T[n] >= l - X[n]][1] = l - X[n];
	while(!pq.empty()){
		int x = pq.top().fi;
		int a, b, c, d;
		tie(a, b, c, d) = pq.top().se; pq.pop();
		if(dist[a][b][c][d] < x)continue;
		if(a > b)continue;
		if(!d){
			int cur = (!d ? X[a - 1] : X[b + 1]);
			int nxt = x + abs(cur - X[a]);
			int tot = c + (nxt <= T[a]);
			if(dist[a + 1][b][tot][0] > nxt){
				dist[a + 1][b][tot][0] = nxt;
				pq.push({nxt, {a + 1, b, tot, 0}});
			}
			nxt = x + min(abs(cur - X[b]), cur + l - X[b]);
			tot = c + (nxt <= T[b]);
			if(dist[a][b - 1][tot][1] > nxt){
				dist[a][b - 1][tot][1] = nxt;
				pq.push({nxt, {a, b - 1, tot, 1}});
			}
		}
		else{
			int cur = (!d ? X[a - 1] : X[b + 1]);
			int nxt = x + min(l - cur + X[a], abs(cur - X[a]));
			int tot = c + (nxt <= T[a]);
			if(dist[a + 1][b][tot][0] > nxt){
				dist[a + 1][b][tot][0] = nxt;
				pq.push({nxt, {a + 1, b, tot, 0}});
			}
			nxt = x + min(abs(cur - X[b]), l - cur + l - X[b]);
			tot = c + (nxt <= T[b]);
			if(dist[a][b - 1][tot][1] > nxt){
				dist[a][b - 1][tot][1] = nxt;
				pq.push({nxt, {a, b - 1, tot, 1}});
			}
		}
	}
	int ans = 0;
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			for(int k = 1; k <= n; k++){
				if(dist[i][j][k][0] < 1e18 || dist[i][j][k][1] < 1e18)ans = max(ans, k);
			}
		}
	}
	cout << ans;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

ho_t3.cpp:74:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   74 | main(){
      | ^~~~

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