Submission #220182

#	Time	Username	Problem	Language	Result	Execution time	Memory
220182		IldarKA	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	135 ms	127480 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;
int n;
long long l, x[202], t[202], dp[202][201][201][2];
int main(){
    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 + 1; i++){
        for(int j = 0; j <= n; j++){
            for(int t = 0; t <= n; t++){
                dp[i][j][t][0] = 1e9 + 1;
                dp[i][j][t][1] = 1e9 + 1;
            }
        }
    }
    x[n + 1] = l;
    dp[n + 1][0][0][0] = 0;
    dp[n + 1][0][0][1] = 0;
    for(int i = n + 1; i >= 1; i--){
        for(int j = 0; j <= n; j++){
            for(int o = 0; o <= min((n + 1) - i + j, n); o++){
                if(dp[i][j][o][0] < 1e9){
                    if(i - 1 > j && x[j] + (l - x[i - 1]) <= 1e9){
                        dp[i - 1][j][o + (x[j] + (l - x[i - 1]) + dp[i][j][o][0] <= t[i - 1])][1] = min(dp[i - 1][j][o + (x[j] + (l - x[i - 1]) + dp[i][j][o][0] <= t[i - 1])][1], x[j] + (l - x[i - 1]) + dp[i][j][o][0]);
                    }
                    if(j + 1 < i){
                        dp[i][j + 1][o + (x[j + 1] - x[j] + dp[i][j][o][0] <= t[j + 1])][0] = min(x[j + 1] - x[j] + dp[i][j][o][0], dp[i][j + 1][o + (x[j + 1] - x[j] + dp[i][j][o][0] <= t[j + 1])][0]);
                    }
                }
                if(dp[i][j][o][1] < 1e9){
                    if(i - 1 > j){
                        dp[i - 1][j][o + ((x[i] - x[i - 1]) + dp[i][j][o][1] <= t[i - 1])][1] = min(dp[i - 1][j][o + ((x[i] - x[i - 1]) + dp[i][j][o][1] <= t[i - 1])][1], (x[i] - x[i - 1]) + dp[i][j][o][1]);
                    }
                    if(j + 1 < i && (l - x[i]) + x[j + 1] <= 1e9){
                        dp[i][j + 1][o + ((l - x[i]) + x[j + 1] + dp[i][j][o][1] <= t[j + 1])][0] = min((l - x[i]) + x[j + 1] + dp[i][j][o][1], dp[i][j + 1][o + ((l - x[i]) + x[j + 1] + dp[i][j][o][1] <= t[j + 1])][0]);
                    }
                }
            }
        }
    }
    int ans = 0;
    for(int i = n + 1; i >= 1; i--){
        for(int j = 0; j <= n; j++){
            for(int o = 0; o <= min((n + 1) - i + j, n); o++){
                if(dp[i][j][o][0] != 1e9 + 1 || dp[i][j][o][1] != 1e9 + 1){
                    //cout << i << " " << j << " " << o << " " << dp[i][j][o][0] << " " << dp[i][j][o][1] << '\n';
                    ans = max(o, ans);
                }
            }
        }
    }
    cout << ans;
}

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