Submission #935449

#TimeUsernameProblemLanguageResultExecution timeMemory
935449weakweakweakCollecting Stamps 3 (JOI20_ho_t3)C++14
100 / 100
68 ms145556 KiB
//自己想到的,好開心(對照過提解了,確定是對的) #include <bits/stdc++.h> using namespace std; #define ll long long int n, l, a[210], t[210]; ll inf = 1e13; ll dp[210][210][210][2]; //dp[l][r][k][w]代表逆時針走過l,順時針走過r,共拿過k個郵票,現在在哪個端點(w=0是左),所需的最短時間 int walk (int st, int ed) { if (st == ed) return 0; if (st > ed) swap(st, ed); return min((a[st] + l - a[ed]), a[ed] - a[st]); } signed main () { ios_base::sync_with_stdio(false); cin.tie(0); memset(dp, 63, sizeof(dp)); dp[0][0][0][0] = dp[0][0][0][1] = 0; cin >> n >> l; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) cin >> t[i]; a[0] = 0, a[n + 1] = l, t[0] = t[n + 1] = -1; int ans = 0; for (int l = 0; l <= n; l++) { for (int r = 0; r <= n and l + r <= n; r++) { for (int k = 0; k <= n; k++) { if (min(dp[l][r][k][1], dp[l][r][k][0]) < inf) { // if (k > ans) cout << l << ' ' << r << ' ' << k << ' ' << dp[l][r][k][0] << ' ' << dp[l][r][k][1] << '\n'; ans = max(ans, k); } //逆時針 if (l + 1 <= n){ ll tt = dp[l][r][k][0] + walk(n + 1 - l, n + 1 - (l + 1)); tt = min(tt, dp[l][r][k][1] + walk(r, n + 1 - (l + 1)) ); if (tt <= t[n + 1 - (l + 1)]) dp[l + 1][r][k + 1][0] = min(dp[l + 1][r][k + 1][0], tt); else dp[l + 1][r][k][0] = min(dp[l + 1][r][k][0], tt); } //順時針 if (r + 1 <= n){ ll tt = dp[l][r][k][0] + walk(n + 1 - l, r + 1); tt = min(tt, dp[l][r][k][1] + walk(r, r + 1) ); if (tt <= t[r + 1]) dp[l][r + 1][k + 1][1] = min(dp[l][r + 1][k + 1][1], tt); else dp[l][r + 1][k][1] = min(dp[l][r + 1][k][1], tt); } } } } cout << ans << '\n'; 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...