Submission #1279807

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279807		yassia	Collecting Stamps 3 (JOI20_ho_t3)	C++20	0 / 100	0 ms	332 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;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
using ld = long double;
using hash_map = gp_hash_table<int, int>;
using hash_set = gp_hash_table<int, null_type>;
auto sd = std::chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(sd);
using ord_set = tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
const ll inf = 1e18;
#define int ll
ll dp[204][205][205][2];

void solve1() {
    ll n;
    cin >> n;
    ll L; cin >> L;
    vector<ll> xi(n);
    vector<ll> ti(n);
    vector<ll> xi1(n);
    for (int i =0; i<n ;i++){
        cin>>xi[i];
    }
    for (int j = 0; j < n; j++){
        xi1[n-1-j] = L - xi[j];
    }

    for (int j =0; j < n; j++){
        cin>>ti[j];
    }
    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] = inf;
                dp[i][j][k][1] = inf;
            }
        }
    }
    xi.insert(xi.begin(), 0);
    xi1.insert(xi1.begin(), 0);
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;

    for (int l = 0; l <= n; l++){
        for (int r = 0; r <= n; r++){
            if (l+r>n)continue;
            for (ll j = 0; j <= n; j++){
                if (dp[j][l][r][0]!=inf){
                    if (l+1<= n &&l+r+1<=n) {
                        ll min_dist= min(xi[l+1]-xi[l], max(0ll,L-(xi[l+1]-xi[l])));
                        bool add = ((dp[j][l][r][0]+min_dist)<=ti[l]);
                        dp[j+add][l+1][r][0] = min(dp[j+add][l+1][r][0], (dp[j][l][r][0]+min_dist));

                    }
                    if (r+1<=n&&l+r+1<=n){
                        ll min_dist= min(xi[l]+xi1[r+1], max(0ll,L-(xi[l]+xi1[r+1])));
                        bool add = ((dp[j][l][r][0] + min_dist)<=ti[r]);
                        dp[j+add][l][r+1][1] = min(dp[j+add][l][r+1][1], (dp[j][l][r][0] + min_dist));
                    }

                }

                if (dp[j][l][r][1] != inf) {
                    if (r+1<=n&&l+r+1<=n){
                        ll min_dist= min(xi1[r+1]-xi1[r], max(0ll,L-(xi1[r+1]-xi1[r])));
                        bool add = ((dp[j][l][r][1] +min_dist)<=ti[r]);
                        dp[j+add][l][r+1][1] = min(dp[j+add][l][r+1][1],(dp[j][l][r][1] + min_dist));
                    }
                    if (l+1<= n&&l+r+1<=n){
                        ll min_dist= min(xi1[r]+xi[l+1], max(0ll,L-(xi1[r]+xi[l+1])));
                        bool add = ((dp[j][l][r][1] + min_dist)<=ti[l]);
                        dp[j+add][l+1][r][0] = min(dp[j+add][l+1][r][0], (dp[j][l][r][1] +min_dist));
                    }
                }
            }
        }
    }
    int answ= 0;
    for (int l =0; l <= n; l++){
        for (int r = 0; r <= n; r++){
            for (int ans =0 ; ans<=min(n,l+r); ans++){
                if (dp[ans][l][r][0]<inf||dp[ans][l][r][1]<inf) answ =max(answ, ans);

            }
        }
    }
    cout<<answ;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
#ifdef local
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif
    int t1 = 1;
    //  cin>>t1;
    for (int o_ = 0; o_ < t1; o_++) {
        solve1();
    }
#ifdef local
    printf_s("\n%.5f s", (double) clock() / CLOCKS_PER_SEC);
#endif
}

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