Submission #499887

#	Time	Username	Problem	Language	Result	Execution time	Memory
499887		Lobo	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	435 ms	557344 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;

/*for ordered_set
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>
*/

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 220

ll n, L, x[2*maxn], t[2*maxn], dist[2*maxn][2*maxn], dp[2*maxn][2*maxn][maxn][2];

void solve() {
    cin >> n >> L;
    for(ii i = 1; i <= n; i++) {
        cin >> x[i];
    }

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

    for(ii i = 1; i <= n; i++) {
        x[i+n] = x[i];
        t[i+n] = t[i];
    }
    x[0] = 0;

    for(ii i = 0; i <= 2*n; i++) {
        for(ii j = 0; j <= 2*n; j++) {
            dist[i][j] = INFll;

            ll x1 = x[i];
            ll x2 = x[j];
            dist[i][j] = min(dist[i][j],abs(x2-x1));

            x1+= L;
            dist[i][j] = min(dist[i][j],abs(x2-x1));
            x1-= L;

            x2+= L;
            dist[i][j] = min(dist[i][j],abs(x2-x1));
            x2-= L;

            for(ii k = 0; k <= n; k++) {
                dp[i][j][k][0] = dp[i][j][k][1] = INFll;
            }
        }
    }

    //sz = size-1 of (l,r)
    //l = begin
    //r = end
    //k = qtd things catch in (l,r)
    //p = 0 -> l; 1 -> r
    //dp[l][r][k][p] -> min time for cover the interval (l,r)
    // with ans = k now in (0->l, 1->r)
    for(ii i = 1; i <= 2*n; i++) {
        ii k = 0;
        if(dist[i][0] <= t[i]) {
            k++;
        }

        dp[i][i][k][0] = dp[i][i][k][1] = dist[i][0];
    }
    for(ii sz = 0; sz < n; sz++) {
        for(ii l = 1; l+sz <= 2*n; l++) {
            ii r = l+sz;

            for(ii k = 0; k <= n; k++) {
                dp[l][r][k][0] = min(dp[l][r][k][0],dp[l][r][k][1]+dist[l][r]);
                dp[l][r][k][1] = min(dp[l][r][k][1],dp[l][r][k][0]+dist[l][r]);

                for(ii p = 0; p <= 1; p++) {
                    ll tmin = dp[l][r][k][p];
                    if(p == 0 && l-1 >= 1) {
                        //pos = l
                        ii l1 = l-1;
                        ii r1 = r;
                        ii p1 = 0;
                        ll tmin1 = dist[l][l1] + tmin;
                        ii k1 = k;
                        if(tmin1 <= t[l1]) k1++;
                        dp[l1][r1][k1][p1] = min(dp[l1][r1][k1][p1],tmin1);

                    }

                    if(p == 1 && r+1 <= 2*n) {
                        //pos = l
                        ii l1 = l;
                        ii r1 = r+1;
                        ii p1 = 1;
                        ll tmin1 = dist[r][r1] + tmin;
                        ii k1 = k;
                        if(tmin1 <= t[r1]) k1++;
                        dp[l1][r1][k1][p1] = min(dp[l1][r1][k1][p1],tmin1);

                    }
                }
            }
        }
    }

    ii ans = 0;

    for(ii sz = 0; sz < n; sz++) {
        for(ii l = 1; l+sz <= 2*n; l++) {
            ii r = l+sz;

            for(ii k = 0; k <= n; k++) {
                for(ii p = 0; p <= 1; p++) {
                    if(dp[l][r][k][p] != INFll) {
                        // cout << l << " " << r << " " << k << " " << p << " == " << dp[l][r][k][p] << endl;
                        ans = max(ans,k);
                    }
                }
            }
        }
    }


    cout << ans << endl;
}

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

    // freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);

    ii tt = 1;
    // cin >> tt;
    while(tt--) solve();

}

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