Zrinka

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 1e18; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0); 
    9    int n; cin >> n;
    10    vector<int> v(n);
    11    for (int i = 0; i < n; i++) cin >> v[i];
    12    int m; cin >> m;
    13    vector<int> a(m);
    14    for (int i = 0; i < m; i++) cin >> a[i];
    15    vector<vector<array<int, 2>>> dp(n + 1, vector<array<int, 2>>(m + 1, {inf, inf}));
    16    auto calc = [&] (int cur, int p) {
    17        return ((cur + 1 & 1) == p ? cur + 1 : cur + 2);
    18    };
    19    dp[0][0][0] = dp[0][0][1] = 0;
    20    for (int i = 0; i <= n; i++) {
    21        for (int j = 0; j <= m; j++) {
    22            if (i > 0) {
    23                dp[i][j][0] = min(calc(dp[i - 1][j][0], v[i - 1]), calc(dp[i - 1][j][1], v[i - 1]));
    24            }
    25            if (j > 0) {
    26                dp[i][j][1] = min(calc(dp[i][j - 1][0], a[j - 1]), calc(dp[i][j - 1][1], a[j - 1]));
    27            }
    28        }
    29    }
    30    cout << min(dp[n][m][0], dp[n][m][1]) << '\n';
    31    return 0;
    32}