Submission #982691

#TimeUsernameProblemLanguageResultExecution timeMemory
982691LOLOLOCollecting Stamps 3 (JOI20_ho_t3)C++17
0 / 100
44 ms145232 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; #define f first #define s second #define pb push_back #define ep emplace #define eb emplace_back #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin()) #define mem(f,x) memset(f , x , sizeof(f)) #define sz(x) (int)(x).size() #define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b)) #define mxx *max_element #define mnn *min_element #define cntbit(x) __builtin_popcountll(x) #define len(x) (int)(x.length()) const int N = 210; ll f[N][N][N][2]; ll x[N], t[N]; void minimize(ll &a, ll b) { if (a > b) a = b; } ll n, l; ll dis(ll a, ll b) { return min(abs(a - b), l - abs(a - b)); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); mem(f, 0x3f); cin >> n >> l; for (int i = 1; i <= n; i++) cin >> x[i]; for (int i = 1; i <= n; i++) cin >> t[i]; x[0] = 0; x[n + 1] = 0; t[0] = -1; t[n + 1] = -1; f[0][0][n + 1][0] = 0; f[0][0][n + 1][1] = 0; int ans = 0; for (int c = 0; c <= n; c++) { for (int i = 0; i <= n + 1; i++) { for (int j = n + 1; j > i; j--) { for (int k = 0; k < 2; k++) { ll pos = k ? x[j] : x[i]; ll lim = k ? t[j] : t[i]; if (i) { if (c) { ll ti = f[c - 1][i - 1][j][0] + dis(x[i - 1], pos); if (ti <= lim) { minimize(f[c][i][j][k], ti); } } minimize(f[c][i][j][k], f[c][i - 1][j][0] + dis(x[i - 1], pos)); } if (j != n + 1) { if (c) { ll ti = f[c - 1][i][j + 1][1] + dis(x[j + 1], pos); if (ti <= lim) { minimize(f[c][i][j][k], ti); } } minimize(f[c][i][j][k], f[c][i][j + 1][1] + dis(x[j + 1], pos)); } if (f[c][i][j][k] <= 1e14) { ans = max(ans, c); } } } } } 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...