Submission #541001

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

ho_t3

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

#define ll long long
#define mp make_pair
#define pii pair<ll,ll>
#define inf (ll)1e15
#define endl "\n"
#define out(x) cout<< #x << " = " << x << endl

int n;
ll L,X[206],T[206];
int isstamp[206];
ll dp[206][206][206][2]; // 已經看過區間(i,j)，拿到了k個stamp，目前人在最左或最右，的最小時間

int goleft(int x){
    return x-1 ? x-1:n;
}
int goright(int x){
    return x==n ? 1:x+1;
}
ll dist(int i,int j){
    return min(abs(X[i]-X[j]), L-abs(X[i]-X[j]));
}
void chmin(ll &a, ll b){
    a = min(a,b);
}
signed main(){
    cin>>n>>L;
    for (int i=1;i<=n;i++) cin>>X[i], isstamp[X[i]] = i;
    for (int i=1;i<=n;i++) cin>>T[i];

    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) for (int k=0;k<=n;k++) dp[i][j][k][0] = dp[i][j][k][1] = inf;

    // check if it is possible to collect all stamps (clockwise or counterclockwise)
    int flag1 = true, flag2 = true;
    for (int i=1;i<=n;i++) if (X[i] > T[i]) flag1 = false;
    for (int i=n;i>=1;i--) if (L-X[i] > T[i]) flag2 = false;
    if (flag1 || flag2){
        cout<<n<<endl;
        return 0;
    }

    
    if (X[1] <= T[1]) dp[1][1][1][0] = dp[1][1][1][1] = X[1];
    else dp[1][1][0][0] = dp[1][1][0][1] = X[1];
    if (L-X[n] <= T[n]) dp[n][n][1][0] = dp[n][n][1][1] = L-X[n];
    else dp[n][n][0][0] = dp[n][n][0][1] = L-X[n];

    for (int d=0;d<n;d++) for (int i=1;i<=n;i++) for (int k=0;k<=d+1;k++){
        int j = i+d > n ? i+d-n : i+d;
        //if (k==6) cout<<i<<"  "<<j<<"  "<<k<<"   "<<dp[i][j][k][0]<<" "<<dp[i][j][k][1]<<endl;
        ll nowtime = dp[i][j][k][0];
        if (nowtime + dist(goleft(i), i) <= T[goleft(i)]){
            chmin(dp[goleft(i)][j][k+1][0],  nowtime + dist(goleft(i), i));
        }
        else chmin(dp[goleft(i)][j][k][0],  nowtime + dist(goleft(i), i));

        if (nowtime + dist(i,goright(j)) <= T[goright(j)]){
            chmin(dp[i][goright(j)][k+1][1], nowtime + dist(i, goright(j)));
        }
        else chmin(dp[i][goright(j)][k][1], nowtime + dist(i, goright(j)));

        
        nowtime = dp[i][j][k][1];
        if (nowtime + dist(goleft(i), j) <= T[goleft(i)]){
            chmin(dp[goleft(i)][j][k+1][0], nowtime + dist(goleft(i), j));
        }
        else chmin(dp[goleft(i)][j][k][0], nowtime + dist(goleft(i), j));

        if (nowtime + dist(j, goright(j)) <= T[goright(j)]){
            chmin(dp[i][goright(j)][k+1][1], nowtime + dist(j, goright(j)));
        }
        else chmin(dp[i][goright(j)][k][1], nowtime + dist(j, goright(j)));
    }

    /*for (int i=1;i<=n;i++) for (int j=1;j<=n;j++){
        int d = j-i < 0 ? j-i+n : j-i;
        for (int k=0;k<=d;k++) if (k==6) cout<<i<<"  "<<j<<"  "<<k<<"   "<<dp[i][j][k][0]<<" "<<dp[i][j][k][1]<<endl;
    }*/
    int best = 0;
    for (int k=0;k<n;k++){
        for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) {
            int d = j-i < 0 ? j-i+n : j-i;
            if (k>d) continue;
            if (dp[i][j][k][0] < inf || dp[i][j][k][1] < inf) best = k;
        }
    }
    cout<<best<<endl;
}

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