Submission #1045006

#TimeUsernameProblemLanguageResultExecution timeMemory
1045006TAhmed33Collecting Stamps 3 (JOI20_ho_t3)C++98
15 / 100
352 ms133268 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize ("trapv") const int inf = 2e9; int dp[203][203][203][2]; int n, l, a[203], t[203]; int ans (int x, int y, int z, int c) { //left, right, count, is it at right? if (x == n + 1 && y == 0) { if (z == 0) return 0; return inf; } if (z < 0) return inf; int &ret = dp[x][y][z][c]; if (ret != -1) return ret; ret = inf; if (c == 0) { if (x != n + 1) { if (y != 0) { int cost = l - a[x] + a[y]; ret = min(ret, ans(x + 1, y, z, 1) + cost); if (ans(x + 1, y, z - 1, 1) + cost <= t[x]) { ret = min(ret, ans(x + 1, y, z - 1, 1) + cost); } } if (x != n + 1) { int cost = a[x + 1] - a[x]; ret = min(ret, ans(x + 1, y, z, 0) + cost); if (ans(x + 1, y, z - 1, 0) + cost <= t[x]) { ret = min(ret, ans(x + 1, y, z - 1, 0) + cost); } } } } else { if (y != 0) { if (x != n + 1) { int cost = l - a[x] + a[y]; ret = min(ret, ans(x, y - 1, z, 0) + cost); if (ans(x, y - 1, z - 1, 0) + cost <= t[y]) { ret = min(ret, ans(x, y - 1, z - 1, 0) + cost); } } if (y != 0) { int cost = a[y] - a[y - 1]; ret = min(ret, ans(x, y - 1, z, 1) + cost); if (ans(x, y - 1, z - 1, 1) + cost <= t[y]) { ret = min(ret, ans(x, y - 1, z - 1, 1) + cost); } } } } return ret; } void solve () { cin >> n >> l; a[0] = 0; a[n + 1] = l; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n; i++) { cin >> t[i]; } memset(dp, -1, sizeof(dp)); int ret = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= n + 1; j++) { for (int k = j + 1; k <= n + 1; k++) { if (ans(k, j, i, 0) != inf || ans(k, j, i, 1) != inf) { ret = i; } } } } cout << ret << '\n'; } signed main () { ios::sync_with_stdio(0); cin.tie(0); int tc = 1; //cin >> tc; while (tc--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...