Submission #769810

#TimeUsernameProblemLanguageResultExecution timeMemory
769810raysh07Collecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
103 ms127484 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define INF (int)1e18 #define f first #define s second mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); const int N = 201; int n, l; int x[N], t[N]; int dp[N][N][N][2]; int f(int x, int y){ int ans = abs(x - y); ans = min(ans, abs(ans - l)); return ans; } void ckmin(int &a, int b){ a = min(a, b); } void Solve() { cin >> n >> l; for (int i = 1; i <= n; i++) cin >> x[i]; for (int i = 1; i <= n; i++) cin >> t[i]; 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] = INF; } } } int t1 = f(0, x[1]); dp[1][n + 1][t1 <= t[1]][0] = t1; int t2 = f(0, x[n]); dp[0][n][t2 <= t[n]][1] = t2; for (int sum = 2; sum <= n; sum++){ for (int i = 0; i < sum; i++){ int j = sum - 1 - i; j = n + 1 - j; for (int tk = 0; tk < sum; tk++){ if (i != 0){ //last = 0 { //go to i + 1 t1 = dp[i][j][tk][0] + f(x[i], x[i + 1]); ckmin(dp[i + 1][j][tk + (t1 <= t[i + 1])][0], t1); } { //go to j - 1 t1 = dp[i][j][tk][0] + f(x[i], x[j - 1]); ckmin(dp[i][j - 1][tk + (t1 <= t[j - 1])][1], t1); } } if (i + 1 != sum){ //last = 1 { //go to i + 1 t1 = dp[i][j][tk][1] + f(x[j], x[i + 1]); ckmin(dp[i + 1][j][tk + (t1 <= t[i + 1])][0], t1); } { //go to j - 1 t1 = dp[i][j][tk][1] + f(x[j], x[j - 1]); ckmin(dp[i][j - 1][tk + (t1 <= t[j - 1])][1], t1); } } } } } int ans = 0; for (int i = 0; i < N; i++){ for (int j = 0; j < N; j++){ for (int k = 0; k < N; k++){ for (int l = 0; l < 2; l++){ if (dp[i][j][k][l] != INF){ ans = max(ans, k); } } } } } cout << ans << "\n"; } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\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...