Submission #1265078

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265078		danglayloi1	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	169 ms	266904 KiB

ho_t3

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=405;
int n, l, a[nx], t[nx], ans=0;
ll dp[205][nx][205][2];
int dis(int u, int v)
{
    if(u<v) return v-u;
    return l-u+v;
}
void mini(ll &x, ll y)
{
    if(x>y) x=y;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>l;
    n++;
    for(int i = 2; i <= n; i++)
        cin>>a[i];
    for(int i = 2; i <= n; i++)
        cin>>t[i];
    a[1]=0, t[1]=-1;
    for(int i = n+1; i <= 2*n; i++)
        a[i]=a[i-n], t[i]=t[i-n];
    memset(dp, 0x3f, sizeof(dp));
    dp[n+1][n+1][0][0]=dp[n+1][n+1][0][1]=0;
    for(int i = n+1; i >= 1; i--)
    {
        for(int j = i; j <= min(2*n, i+n-1); j++)
        {
            for(int k = 0; k <= n; k++)
            {
                ll tim=dp[i][j][k][0];
                mini(dp[i-1][j][k+(tim+dis(a[i-1], a[i])<=t[i-1])][0], tim+dis(a[i-1], a[i]));
                mini(dp[i][j+1][k+(tim+dis(a[i], a[j+1])<=t[j+1])][1], tim+dis(a[i], a[j+1]));
                tim=dp[i][j][k][1];
                mini(dp[i][j+1][k+(tim+dis(a[j], a[j+1])<=t[j+1])][1], tim+dis(a[j], a[j+1]));
                mini(dp[i-1][j][k+(tim+dis(a[i-1], a[j])<=t[i-1])][0], tim+dis(a[i-1], a[j]));
            }
        }
    }
    for(int i = n+1; i >= 1; i--)
        for(int j = i; j <= min(2*n, i+n-1); j++)
            for(int k = 0; k <= n; k++)
                if(min(dp[i][j][k][0], dp[i][j][k][1])<inf) ans=max(ans, k);
    cout<<ans;
}

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