Submission #285576

#TimeUsernameProblemLanguageResultExecution timeMemory
285576kaplanbarCollecting Stamps 3 (JOI20_ho_t3)C++14
100 / 100
182 ms135416 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; constexpr int N = 205; int n, m; ll x[2*N], t[2*N], dp[N][N][N][2]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 0; i < n; i++) { cin >> x[i]; } for(int i = 0; i < n; i++) { cin >> t[i]; } auto dist = [&](int now, int next) { int d = min(m - now, now); d += min(next, m - next); return min(abs(now - next), d); }; x[n] = 0; t[n] = 1e9; for(int i = 1; i <= n; i++) { x[n + i] = x[i - 1]; t[n + i] = t[i - 1]; } for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) for(int k = 0; k < N; k++) dp[i][j][k][0] = dp[i][j][k][1] = 1e18; dp[0][0][0][0] = dp[0][0][0][1] = 0; for(int l = 0; l <= n; l++) { for(int r = 0; l + r < n; r++) { if(l == n || r == n) continue; for(int cnt = 0; cnt <= l + r; cnt++) { for(int dir = 0; dir <= 1; dir++) { if(dp[l][r][cnt][dir] == 1e18) continue; int now = dir ? x[n + r] : x[n - l]; int next = x[n + r + 1]; ll tim = t[n + r + 1]; ll tum = dp[l][r][cnt][dir] + dist(now, next); dp[l][r + 1][cnt + (tum <= tim)][1] = min(dp[l][r + 1][cnt + (tum <= tim)][1], tum); next = x[n - l - 1]; tim = t[n - l - 1]; tum = dp[l][r][cnt][dir] + dist(now, next); dp[l + 1][r][cnt + (tum <= tim)][0] = min(dp[l + 1][r][cnt + (tum <= tim)][0], tum); } } } } int ans = 0; for(int l = 0; l <= n; l++) for(int r = 0; r <= n; r++) for(int cnt = 0; cnt <= l + r; cnt++) { if(dp[l][r][cnt][0] < 1e18 || dp[l][r][cnt][1] < 1e18) ans = max(ans, cnt); } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...