Submission #1182394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182394		anteknne	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	80 ms	139416 KiB

ho_t3

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

#define pb push_back
#define pii pair<ll, ll>
#define pll pair<ll, ll>
#define st first
#define nd second
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define debug false

const int MAXN = 200 + 7;
ll dp[MAXN][MAXN][MAXN][2];
ll x[MAXN];
ll t[MAXN];
int l;

void czysc () {
    for (int i = 0; i < MAXN; i ++) {
        for (int j = 0; j < MAXN; j ++) {
            for (int k = 0; k < MAXN; k ++) {
                for (int l = 0; l < 2; l ++) {
                    dp[i][j][k][l] = LLONG_MAX;
                }
            }
        }
    }
}

ll odl (int i, int j) {
    return min(abs(x[i] - x[j]), min(x[i], l - x[i]) + min(x[j], l - x[j]));
}

int main () {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin >> n >> l;

    for (int i = 1; i <= n; i ++) {
        cin >> x[i];
    }

    for (int i = 1; i <= n; i ++) {
        cin >> t[i];
    }

    czysc();

    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    dp[0][n + 1][0][0] = 0;
    dp[0][n + 1][0][1] = 0;

    //po i -> 0
    //po j -> 1


    int wyn = 0;
    for (int i = 0; i <= n; i ++) {
        for (int j = n + 1; j > i; j --) {
            for (int k = 0; k <= n + 1 - j + i; k ++) {
                ll t0 = dp[i][j][k][0];
                ll t1 = dp[i][j][k][1];
                if (t0 != LLONG_MAX) {
                    wyn = max(wyn, k);
                    dp[i + 1][j][k + (odl(i, i + 1) + t0 <= t[i + 1])][0] = min(dp[i + 1][j][k + (odl(i, i + 1) + t0 <= t[i + 1])][0], t0 + odl(i, i + 1));
                    dp[i][j - 1][k + (odl(i, j - 1) + t0 <= t[j - 1])][1] = min(dp[i][j - 1][k + (odl(i, j - 1) + t0 <= t[j - 1])][1], t0 + odl(i, j - 1));
                    //cout << i << " " << j - 1 << " " << k + (odl(i, j - 1) + t0 <= t[j - 1]) << " " << odl(i, j - 1) << "\n";
                }
                if (t1 != LLONG_MAX) {
                    wyn = max(wyn, k);
                    dp[i][j - 1][k + (odl(j, j - 1) + t1 <= t[j - 1])][1] = min(dp[i][j - 1][k + (odl(j, j - 1) + t1 <= t[j - 1])][1], t1 + odl(j, j - 1));
                    dp[i + 1][j][k + (odl(j, i + 1) + t1 <= t[i + 1])][0] = min(dp[i + 1][j][k + (odl(j, i + 1) + t1 <= t[i + 1])][0], t1 + odl(j, i + 1));
                }
                //cout << i << " " << j << " " << k << ": " << dp[i][j][k][0] << " " << dp[i][j][k][1] << "\n";
            }
        }
    }

    cout << wyn << "\n";




    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75