Submission #861017

#	Time	Username	Problem	Language	Result	Execution time	Memory
861017		phoenix0423	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	30 ms	67028 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define lowbit(x) x&-x
#define ckmin(a, b) a = min(a, b)
#define ckmax(a, b) a = max(a, b)
const int maxn = 4e5 + 5;
const int INF = 1e9 + 7;
int dp[205][205][2][205]; // 0 = l, 1 = r
int x[205], t[205];

int main(void){
	fastio;
	int n, l;
	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 + 1; i++) for(int j = 0; j <= n + 1; j++) for(int d = 0; d < 2; d++) for(int k = 0; k <= n; k++) dp[i][j][d][k] = INF;
	dp[1][n + 1][0][(x[1] <= t[1])] = x[1];
	dp[0][n][1][(l - x[n] <= t[n])] = l - x[n];
	x[0] = x[n] - l, x[n + 1] = x[1] + l;
	for(int len = 1; len <= n; len++){
		for(int i = 0; i <= len; i++){
			int j = n + 1 - (len - i);
			for(int cnt = 0; cnt <= len; cnt++){
				int t1 = dp[i][j][0][cnt], t2 = dp[i][j][1][cnt];
				ckmin(dp[i + 1][j][0][cnt + (t1 + (x[i + 1] - x[i]) <= t[i + 1])], t1 + (x[i + 1] - x[i]));
				ckmin(dp[i + 1][j][0][cnt + (t2 + (l - x[j] + x[i + 1]) <= t[i + 1])], t2 + (l - x[j] + x[i + 1]));
				ckmin(dp[i][j - 1][1][cnt + (t1 + (x[i] + l - x[j - 1]) <= t[j - 1])], t1 + (x[i] + l - x[j - 1]));
				ckmin(dp[i][j - 1][1][cnt + (t2 + (x[j] - x[j - 1]) <= t[j - 1])], t2 + (x[j] - x[j - 1]));
			}
		}
	}
	int ans = 0;
	for(int i = 0; i <= n; i++){
		for(int d = 0; d < 2; d++){
			for(int cnt = 1; cnt <= n; cnt++){
				if(dp[i][i + 1][d][cnt] < INF) ans = max(ans, cnt);
			}
		}
	}
	cout<<ans<<"\n";
}

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