Submission #680944

#	Time	Username	Problem	Language	Result	Execution time	Memory
680944		Tuanlinh123	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	1 ms	852 KiB

ho_t3

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second

using namespace std;

#define LOCALIO "C:/Users/admin/Documents/Code/"

const ll INF=1000000000000000000;
ll n, L, a[205], t[205], res;
ll dp[205][205][205][2];
bool check[205][205][205][2];

ll dis(ll l, ll r, ll di)
{
    ll Max=max(l, r), Min=min(l, r);
    return min(a[Max]-a[Min], a[Min]-a[Max]+L);
}

ll calc(ll l, ll r, ll k, ll di)
{
    if (k<0) return INF;
    if (check[l][r][k][di])
        return dp[l][r][k][di];
    if (l==r) 
        return dp[l][r][k][di];
    ll ans=INF;
    if (!di)
    {
        ll A=calc((l+1)%n, r, k-1, 0);
        ll B=calc((l+1)%n, r, k, 0);
        ll C=calc((l+1)%n, r, k-1, 1);
        ll D=calc((l+1)%n, r, k, 1);
        ll dis1=dis((l+1)%n, l, 1), dis2=dis(r, l, 1);
        if (t[l]>=A+dis1)
            ans=min(ans, A+dis1);
        if (t[l]<B+dis1)
            ans=min(ans, B+dis1);
        if (t[l]>=C+dis2)
            ans=min(ans, C+dis2);
        if (t[l]<D+dis2)
            ans=min(ans, D+dis2);
    }
    else
    {
        ll A=calc(l, (r-1+n)%n, k-1, 0);
        ll B=calc(l, (r-1+n)%n, k, 0);
        ll C=calc(l, (r-1+n)%n, k-1, 1);
        ll D=calc(l, (r-1+n)%n, k, 1);
        ll dis1=dis((r-1+n)%n, r, 0), dis2=dis(l, r, 0);
        if (t[r]>=A+dis2)
            ans=min(ans, A+dis2);
        if (t[r]<B+dis2)
            ans=min(ans, B+dis2);
        if (t[r]>=C+dis1)
            ans=min(ans, C+dis1);
        if (t[r]<D+dis1)
            ans=min(ans, D+dis1);
    }
    dp[l][r][k][di]=ans;
    check[l][r][k][di]=1;
    // if (ans!=INF)
    //     cout << l << " " << r << " " << k << " " << di << " " << ans << "\n";
    if (l==(r+1)%n && ans!=INF)
        res=max(res, k);
    return ans;
}

int main()
{
    #ifdef LOCAL
        freopen( LOCALIO "input.txt","r",stdin) ;
        freopen( LOCALIO "output.txt","w",stdout) ;
    #endif

    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
//	freopen("FIBONACCI.inp","r",stdin);
//	freopen("FIBONACCI.out","w",stdout);
    cin >> n >> L;
    for (ll i=0; i<n; i++)
        cin >> a[i];
    for (ll i=0; i<n; i++)
        cin >> t[i];
    for (ll i=0; i<n; i++)
        for (ll j=0; j<n; j++)
            for (ll k=0; k<=n; k++)
                for (ll di=0; di<2; di++)
                    dp[i][j][k][di]=INF;
    dp[0][0][t[0]>=a[0]][0]=a[0];
    dp[n-1][n-1][t[n-1]>=L-a[n-1]][0]=L-a[n-1];
    for (ll i=0; i<n; i++)
        for (ll j=0; j<n; j++)
            for (ll k=0; k<=n; k++)
                for (ll z=0; z<2; z++)
                    calc(i, j, k, z);
    cout << res;
}

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