Submission #373178

#	Time	Username	Problem	Language	Result	Execution time	Memory
373178		Leonardo_Paes	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	148 ms	67692 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e2+10;
const int inf = 1e9;
int dp[maxn][maxn][maxn][2], x[maxn], t[maxn];

int main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n, l;
    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=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] = inf;
            }
        }
    }
    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    auto prv = [&](int x){
        if(x-1 < 1) return n;
        return x-1;
    };
    auto nxt = [&](int x){
        if(x+1 > n) return 1;
        return x+1;
    };
    auto d = [&](int a, int b){
        if(a > b) swap(a, b);
        return min(x[b] - x[a], l - x[b] + x[a]);
    };
    auto min_self = [&](int &a, int &b){
        a = min(a, b);
    };
    for(int len=0; len<n; len++){
        for(int i=0; i<=n; i++){
            for(int k=0; k<=len; k++){
                int j = (i + len)%(n+1);
                //l -> l
                int tt = dp[i][j][k][0] + d(prv(i), i);
                min_self(dp[prv(i)][j][k+(tt <= t[prv(i)])][0], tt);
                //r -> l
                tt = dp[i][j][k][1] + d(prv(i), j);
                min_self(dp[prv(i)][j][k+(tt <= t[prv(i)])][0], tt);
                //l -> r
                tt = dp[i][j][k][0] + d(i, nxt(j));
                min_self(dp[i][nxt(j)][k+(tt <= t[nxt(j)])][1], tt);
                //r -> r
                tt = dp[i][j][k][1] + d(j, nxt(j));
                min_self(dp[i][nxt(j)][k+(tt <= t[nxt(j)])][1], tt);
            }
        }
    }
    int ans = 0;
    for(int i=0; i<=n; i++){
        for(int j=0; j<=n; j++){
            for(int k=0; k<=n; k++){
                for(int q : {0, 1}){
                    if(dp[i][j][k][q] != inf) ans = max(ans, k);
                }
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

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