Submission #541050

#	Time	Username	Problem	Language	Result	Execution time	Memory
541050		Cookie197	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	158 ms	130124 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];
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){
    if (i<j) return X[j] - X[i];
    return X[j] - X[i] + L;
}
void chmin(ll &a, ll b){
    a = min(a,b);
}
signed main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>L;
    for (int i=1;i<=n;i++) cin>>X[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;

    
    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;

        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++) ;//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;
        }
    }
    // 全部可選的特判？
    for (int i=1;i<=n;i++){
        if (dp[i][goleft(i)][n][0] < inf || dp[i][goleft(i)][n][1] < inf) best = n;
        if (dp[i][goright(i)][n][0] < inf || dp[i][goright(i)][n][1] < inf) best = n;
    }
    cout<<best<<endl;
}

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