Submission #1176787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176787		LmaoLmao	Collecting Stamps 3 (JOI20_ho_t3)	C++20	0 / 100	0 ms	320 KiB

ho_t3

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;

const int N = 1e5;
const int INF = 1e9;

int dp[205][205][205][2];
int a[205];
int ti[205];
int n,l;

int dist(int x,int y) {
    if(x<y) swap(x,y);
    return min(x-y,l-x+y);
}
int get(int x,int y) {
    if(x+y>n) return (x+y)%n;
    return x+y;
}

void solve(int i,int j,int k) {
    int t=get(i+1,j-2);
    int cur=get(i,1);
    int tmp=min(dp[cur][j-1][k][0]+dist(a[i],a[cur]),dp[cur][j-1][k][1]+dist(a[i],a[t]));
    if(tmp<=ti[i]) {
        dp[i][j][k+1][0]=min(dp[i][j][k+1][0],tmp);
    }
    //cout << dp[i][j][k+1][0] << endl;
    dp[i][j][k][0]=min(dp[i][j][k][0],tmp);
    t=get(i,j-2);
    cur=get(i,j-1);
    tmp=min(dp[i][j-1][k][0]+dist(a[i],a[cur]),dp[i][j-1][k][1]+dist(a[t],a[cur]));
    if(tmp<=ti[i]) {
        dp[i][j][k+1][1]=min(dp[i][j][k+1][1],tmp);
    }
    //cout << dp[i][j][k+1][1] << ' ' << tmp << end;
    dp[i][j][k][1]=min(dp[i][j][k][1],tmp);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> l;
    for(int i=1;i<=n;i++) {
        cin >> a[i];
    }
    for(int i=1;i<=n;i++) {
        cin >> ti[i];
    }
    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]=dp[i][j][k][1]=1e18;
        }
    }
    if(1) {
        bool x=(min(l-a[1],a[1])<=ti[1]);
        dp[1][1][x][0]=min(n-a[1],a[1]);
        dp[1][1][x][1]=min(n-a[1],a[1]);
        x=(min(l-a[n],a[n])<=ti[n]);
        dp[n][1][x][0]=min(l-a[n],a[n]);
        dp[n][1][x][1]=min(l-a[n],a[n]);
    }
    int ans=0;
    for(int j=2;j<=n;j++) {
        for(int i=1;i<=n;i++) {
            for(int k=j;k>=0;k--) {
                solve(i,j,k);
            }
            for(int k=0;k<=j;k++) {
                if(j==n && min(dp[i][j][k][0],dp[i][j][k][1])<1e18) {
                    ans=max(ans,k);
                }
            }
        }
    }
    solve(5,2,1);
    cout << ans;
    return 0;
}

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