Submission #1309177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309177		IUA_Hasin	Marathon Race 2 (JOI24_ho_t3)	C++20	0 / 100	0 ms	332 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;
const ll INF = 1e18;

// dp[len][i][side]: min weighted distance to cover a range of length 'len' 
// starting at index 'i', ending at left (side=0) or right (side=1).
ll dp[2005][2005][2];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N; ll L;
    cin >> N >> L;
    vector<ll> X(N + 1);
    for (int i = 1; i <= N; i++) cin >> X[i];
    sort(X.begin() + 1, X.end());

    int Q; cin >> Q;
    while (Q--) {
        ll S, G, T;
        cin >> S >> G >> T;

        // Reset DP for each scenario (only feasible for Q <= 10)
        // If Q is large, we need the O(N) approach below.
        for (int i = 1; i <= N; i++) {
            dp[1][i][0] = dp[1][i][1] = abs(S - X[i]);
        }

        for (int len = 1; len < N; len++) {
            for (int i = 1; i + len - 1 <= N; i++) {
                int j = i + len - 1;
                if (dp[len][i][0] >= INF && dp[len][i][1] >= INF) continue;

                // Move from left end (i) to i-1 or j+1
                if (i > 1) {
                    dp[len+1][i-1][0] = min(dp[len+1][i-1][0], dp[len][i][0] + (ll)(len + 1) * (X[i] - X[i-1]));
                }
                if (j < N) {
                    dp[len+1][i][1] = min(dp[len+1][i][1], dp[len][i][0] + (ll)(len + 1) * (X[j+1] - X[i]));
                }
                // Move from right end (j) to i-1 or j+1
                if (i > 1) {
                    dp[len+1][i-1][0] = min(dp[len+1][i-1][0], dp[len][i][1] + (ll)(len + 1) * (X[j] - X[i-1]));
                }
                if (j < N) {
                    dp[len+1][i][1] = min(dp[len+1][i][1], dp[len][i][1] + (ll)(len + 1) * (X[j+1] - X[j]));
                }
            }
        }

        ll min_travel = min(dp[N][1][0] + (ll)(N + 1) * abs(X[1] - G), 
                            dp[N][1][1] + (ll)(N + 1) * abs(X[N] - G));
        
        if (N + min_travel <= T) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 10
• Subtask 4: 0 / 28
• Subtask 5: 0 / 10
• Subtask 6: 0 / 19
• Subtask 7: 0 / 19