Submission #1309175

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309175		IUA_Hasin	Marathon Race 2 (JOI24_ho_t3)	C++20	7 / 100	1 ms	588 KiB

Main

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

using namespace std;

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

// For large N, we need an observation: the path will always be 
// S -> (some sequence picking up all balls) -> G.
// The cost is N + dist(S, P1) + 2*dist(P1, P2) + ... + (N+1)*dist(PN, G).

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

    int N;
    ll L;
    if (!(cin >> N >> L)) return 0;

    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;

        // For the subtasks where N is small, we can use the DP logic.
        // For large N, we evaluate the two primary strategies:
        // 1. S -> X[1] -> X[N] -> G
        // 2. S -> X[N] -> X[1] -> G
        
        auto calculate = [&](ll start, ll end1, ll end2, ll goal) {
            ll time = N; // 1 sec per ball 
            
            // Movement: Start to first extreme
            time += abs(start - end1); 
            
            // Movement: First extreme to second extreme (collecting others)
            // Weight increases as we pick up balls.
            // In the simple path end1 -> end2, we pick up balls along the way.
            ll travel = abs(end1 - end2);
            ll current_pos = end1;
            int balls_carried = 1;
            
            // This is a simplified model for the two-path strategy
            // The time is actually: dist(S, P1)*1 + dist(P1, P2)*2 ... + dist(PN, G)*(N+1)
            // For the path S -> X[1] -> X[N] -> G:
            ll total_dist_time = abs(X[1] - S);
            for(int i = 1; i < N; ++i) {
                total_dist_time += (ll)(i + 1) * (X[i+1] - X[i]);
            }
            total_dist_time += (ll)(N + 1) * abs(G - X[N]);
            
            return N + total_dist_time;
        };

        ll time1 = 0;
        // Strategy 1: S -> X[1] -> ... -> X[N] -> G
        time1 = N + abs(X[1] - S);
        for(int i = 1; i < N; i++) time1 += (ll)(i + 1) * (X[i+1] - X[i]);
        time1 += (ll)(N + 1) * abs(G - X[N]);

        // Strategy 2: S -> X[N] -> ... -> X[1] -> G
        ll time2 = N + abs(S - X[N]);
        for(int i = N; i > 1; i--) time2 += (ll)(N - i + 2) * (X[i] - X[i-1]);
        time2 += (ll)(N + 1) * abs(G - X[1]);

        if (min(time1, time2) <= T) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}

• Subtask 1: 7 / 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