Submission #1176803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176803		LmaoLmao	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	112 ms	130900 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<ll, ll>;
using aa = array<int,3>;

const int N = 1e6+1;
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[cur]) {
        dp[i][j][k+1][1]=min(dp[i][j][k+1][1],tmp);
    }
    //cout << dp[1][1][1][0] << endl;;
    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;
        }
    }
    int ans=0;
    if(1) {
        int x=(min(l-a[1],a[1])<=ti[1]);
        dp[1][1][x][0]=min(l-a[1],a[1]);
        dp[1][1][x][1]=min(l-a[1],a[1]);
        ans=x;
        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]);
        ans=max(ans,x);
    }
    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(min(dp[i][j][k][0],dp[i][j][k][1])<1e18) {
                    ans=max(ans,k);
                }
                //cout << i << ' ' << j << ' ' << k << ' ' << min(dp[i][j][k][0],dp[i][j][k][1]) << endl;
            }
        }
    }
    //solve(1,2,1);
    cout << ans << '\n';
    return 0;
}

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