Submission #982782

#TimeUsernameProblemLanguageResultExecution timeMemory
982782LOLOLOCollecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
123 ms145640 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 = 0; i <= n + 1; i++) { for (int j = 0; j <= n + 1; j++) { for (int k = 0; k <= n + 1; k++) { f[i][j][k][0] = f[i][j][k][1] = 1e15; } } } 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] = l; 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--) { if (i) { if (c) { ll ti = min(f[c - 1][i - 1][j][0] + dis(x[i - 1], x[i]), f[c - 1][i - 1][j][1] + dis(x[j], x[i])); if (ti <= t[i]) minimize(f[c][i][j][0], ti); } minimize(f[c][i][j][0], min(f[c][i - 1][j][0] + dis(x[i - 1], x[i]), f[c][i - 1][j][1] + dis(x[j], x[i]))); } if (j != n + 1) { if (c) { ll ti = min(f[c - 1][i][j + 1][1] + dis(x[j + 1], x[j]), f[c - 1][i][j + 1][0] + dis(x[j], x[i])); if (ti <= t[j]) minimize(f[c][i][j][1], ti); } minimize(f[c][i][j][1], min(f[c][i][j + 1][1] + dis(x[j + 1], x[j]), f[c][i][j + 1][0] + dis(x[j], x[i]))); } if (min(f[c][i][i][0], f[c][i][j][1]) < 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...