Submission #681001

#	Time	Username	Problem	Language	Result	Execution time	Memory
681001		Tuanlinh123	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	433 ms	74600 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 int INF=1000000005;
int n, L, a[205], t[205], res;
int dp[205][205][205][2];
bool check[205][205][205][2];
 
int dis(int l, int r, int di)
{
    if (!di)
    {
        if (r<l)
            return a[r]-a[l]+L;
        return a[r]-a[l];
    }
    if (r>l)
        return a[l]-a[r]+L;
    return a[l]-a[r];
}

bool test(ll l, ll r)
{
    if (l>r) l-=n;
    if (l<=0 && r>=0)
        return 1;
    if (l<=n-1 && r>=n-1)
        return 1;
    return 0;
}
 
int calc(int l, int r, int k, int di)
{
    if (!test(l, r))
        return INF;
    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];
    int ans=INF;
    if (!di)
    {
        int A=calc((l+1)%n, r, k-1, 0);
        int B=calc((l+1)%n, r, k, 0);
        int C=calc((l+1)%n, r, k-1, 1);
        int D=calc((l+1)%n, r, k, 1);
        int dis1=dis((l+1)%n, l, 1), dis2=dis(r, l, 1);
        if (t[l]>=A+dis1)
            ans=min(ans, A+dis1);
        ans=min(ans, B+dis1);
        if (t[l]>=C+dis2)
            ans=min(ans, C+dis2);
        ans=min(ans, D+dis2);
    }
    else
    {
        int A=calc(l, (r-1+n)%n, k-1, 0);
        int B=calc(l, (r-1+n)%n, k, 0);
        int C=calc(l, (r-1+n)%n, k-1, 1);
        int D=calc(l, (r-1+n)%n, k, 1);
        int dis1=dis((r-1+n)%n, r, 0), dis2=dis(l, r, 0);
        if (t[r]>=A+dis2)
            ans=min(ans, A+dis2);
        ans=min(ans, B+dis2);
        if (t[r]>=C+dis1)
            ans=min(ans, C+dis1);
        ans=min(ans, D+dis1);
    }
    dp[l][r][k][di]=ans;
    check[l][r][k][di]=1;
    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 (int i=0; i<n; i++)
        cin >> a[i];
    for (int i=0; i<n; i++)
        cin >> t[i];
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            for (int k=0; k<=n; k++)
                for (int di=0; di<2; di++)
                    dp[i][j][k][di]=INF;
    if (t[0]>=a[0] || t[n-1]>=L-a[n-1])
        res=1;
    dp[0][0][t[0]>=a[0]][0]=a[0];
    dp[0][0][0][0]=a[0];
    dp[n-1][n-1][t[n-1]>=L-a[n-1]][0]=L-a[n-1];
    dp[n-1][n-1][0][0]=L-a[n-1];
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
            for (int k=0; k<=n; k++)
                calc(i, j, k, 0), calc(i, j, k, 1);
    cout << res;
}

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