Submission #815355

#	Time	Username	Problem	Language	Result	Execution time	Memory
815355		Charizard2021	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	0 ms	212 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, l;
    cin >> n >> l;
    int x[1 + n];
    int t[1 + n];
    for (int i = 1; i <= n; i++){
        cin >> x[i];
    }
    for (int i = 1; i <= n; i++){
        cin >> t[i];
    }
    int dp[n][n][n][2];
    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] = INT_MAX;
                dp[i][j][k][1] = INT_MAX;
            }
        }
    }
    int val = abs(x[1]);
    val = min(val, abs(val - l));
    dp[1][n + 1][val <= t[1]][0] = val;
    int val2 = abs(x[n]);
    val2 = min(val2, abs(val2 - l));
    dp[0][n][val2 <= t[n]][1] = val2;
    for (int sum = 2; sum <= n; sum++){
        for (int i = 0; i < sum; i++){
            int j = sum - 1 - i;
            j = n + 1 - (sum - 1 - i);
            for(int k = 0; k < sum; k++){
                if(i != 0){
                    int val4 = abs(x[i] - x[i + 1]);
                    val4 = min(val4, abs(val4 - l));
                    int val3 = dp[i][j][k][0] + val4;
                    dp[i + 1][j][k + (val3 <= t[i + 1])][0] = min(dp[i + 1][j][k + (val3 <= t[i + 1])][0], val3);
                    int val6 = abs(x[i] - x[j - 1]);
                    val6 = min(val6, abs(val6 - l));
                    int val5 = dp[i][j][k][0] + val6;
                    dp[i][j - 1][k + (val5 <= t[j - 1])][1] = min(dp[i][j - 1][k + (val5 <= t[j - 1])][1], val5);
                }
                if(i + 1 != sum){
                    int val4 = abs(x[j] - x[i + 1]);
                    val4 = min(val4, abs(val4 - l));
                    int val3 = dp[i][j][k][1] + val4;
                    dp[i + 1][j][k + (val3 <= t[i + 1])][0] = min(dp[i + 1][j][k + (val3 <= t[i + 1])][0], val3);
                    int val6 = abs(x[j] - x[j - 1]);
                    val6 = min(val6, abs(val6 - l));
                    int val5 = dp[i][j][k][1] + val6;
                    dp[i][j - 1][k + (val5 <= t[j - 1])][1] = min(dp[i][j - 1][k + (val5 <= t[j - 1])][1], val5);
                }
            }
        }
    }
    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 l = 0; l < 2; l++){
                    if (dp[i][j][k][l] != INT_MAX){
                        ans = max(ans, k);
                    }
                }
            }
        }
    }
    cout << ans << "\n";
}

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