Submission #222766

#	Time	Username	Problem	Language	Result	Execution time	Memory
222766		jovan_b	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	158 ms	129784 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

ll dp[205][205][2][205];

const ll INF = 1e15;

ll a[205];
ll b[205];

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    ll n, l;
    cin >> n >> l;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    for(int i=1; i<=n; i++){
        cin >> b[i];
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=0; k<=1; k++){
                for(int r=0; r<=n; r++){
                    dp[i][j][k][r] = INF;
                }
            }
        }
    }
    dp[1][1][1][(b[1] >= a[1])] = a[1];
    dp[n][n][0][(b[n] >= l-a[n])] = l-a[n];
    for(int len=1; len<n; len++){
        for(int i=n; i>=1; i--){
            int ost = len-(n-i+1);
            if(ost <= 0) break;
            int j = ost;
            for(int k=0; k<=n; k++){
                ll vreme = dp[i][j][0][k];
                int novi = (vreme+a[i]-a[i-1] <= b[i-1]) + k;
                dp[i-1][j][0][novi] = min(dp[i-1][j][0][novi], vreme+a[i]-a[i-1]);
                novi = (vreme+l-a[i]+a[j+1] <= b[j+1]) + k;
                dp[i][j+1][1][novi] = min(dp[i][j+1][1][novi], vreme+l-a[i]+a[j+1]);
                vreme = dp[i][j][1][k];
                novi = (vreme+a[j+1]-a[j] <= b[j+1]) + k;
                dp[i][j+1][1][novi] = min(dp[i][j+1][1][novi], vreme+a[j+1]-a[j]);
                novi = (vreme+l-a[i-1]+a[j] <= b[i-1]) + k;
                dp[i-1][j][0][novi] = min(dp[i-1][j][0][novi], vreme+l-a[i-1]+a[j]);
            }
        }
        for(int k=0; k<=n; k++){
            ll vreme = dp[1][len][1][k];
            int novi = (vreme+a[len+1]-a[len] <= b[len+1]) + k;
            dp[1][len+1][1][novi] = min(dp[1][len+1][1][novi], vreme+a[len+1]-a[len]);
            novi = (vreme+l-a[n]+a[len] <= b[n]) + k;
            dp[n][len][0][novi] = min(dp[n][len][0][novi], vreme+l-a[n]+a[len]);
            int j = n-len+1;
            vreme = dp[j][n][0][k];
            novi = (vreme+a[j]-a[j-1] <= b[j-1]) + k;
            dp[j-1][n][0][novi] = min(dp[j-1][n][0][novi], vreme+a[j]-a[j-1]);
            novi = (vreme+a[1]+l-a[j] <= b[1]) + k;
            dp[j][1][1][novi] = min(dp[j][1][1][novi], vreme+a[1]+l-a[j]);
        }
    }
    //cout << dp[5][5][0][1] << endl;
    int res = 0;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=0; k<=1; k++){
                for(int r=0; r<=n; r++){
                    if(dp[i][j][k][r] != INF) res = max(res, r);
                    //if(r == 5 && dp[i][j][k][r] != INF) cout << i << " " << j << " " << k << " " << dp[i][j][k][r] << endl;
                }
            }
        }
    }
    cout << res;
    return 0;
}

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