Submission #1300305

#TimeUsernameProblemLanguageResultExecution timeMemory
1300305trantrungkeinSemiexpress (JOI17_semiexpress)C++20
100 / 100
74 ms33272 KiB
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Sử dụng long long vì T có thể lên tới 10^18 và tính toán thời gian dễ tràn int
typedef long long ll;

int main() {
    // Tối ưu I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll N, M, K;
    cin >> N >> M >> K;

    ll A, B, C;
    cin >> A >> B >> C; // A: Local, B: Express, C: Semiexpress

    ll T;
    cin >> T;

    vector<ll> S(M);
    for (int i = 0; i < M; i++) {
        cin >> S[i];
    }

    // Danh sách lưu trữ số lượng ga "cứu thêm được" nếu dùng quyền đặt trạm Semiexpress
    vector<ll> gains;
    
    // Biến lưu tổng số ga đi được (khởi tạo -1 để trừ ga số 1 vì đề bài yêu cầu "ngoại trừ ga 1")
    // Tuy nhiên cách tính bên dưới sẽ cộng dồn từng đoạn, ta sẽ xử lý việc trừ ga 1 sau.
    // Logic an toàn: Đếm tất cả các ga đi được (bao gồm ga 1), cuối cùng trừ 1.
    ll total_stations = 0;

    // Duyệt qua từng khoảng giữa 2 trạm Tốc hành [S[i], S[i+1])
    for (int i = 0; i < M - 1; i++) {
        ll start = S[i];
        ll next_stop = S[i+1];
        
        // Thời gian để tàu Tốc hành đến được ga S[i]
        // S[i] là chỉ số 1-based, khoảng cách từ 1 là S[i]-1
        ll time_at_start = (start - 1) * B;
        
        // Nếu ngay cả tàu Tốc hành đến S[i] cũng đã quá giờ thì không làm được gì ở đoạn này
        if (time_at_start > T) continue;

        // --- PHẦN 1: Tính số ga đi được từ S[i] bằng Tàu thường (Miễn phí) ---
        ll time_remain = T - time_at_start;
        ll dist_local = time_remain / A; // Số bước đi được bằng tàu thường
        
        // Vị trí xa nhất đi được từ start (không vượt quá next_stop - 1)
        ll current_reach = min(next_stop - 1, start + dist_local);
        
        // Cộng số lượng ga đi được vào tổng (đoạn [start, current_reach])
        total_stations += (current_reach - start + 1);

        // --- PHẦN 2: Tính tiềm năng nếu đặt thêm trạm Semiexpress ---
        // Chỉ xét nếu vẫn chưa phủ hết đoạn này
        
        // Điểm bắt đầu cho trạm Semiexpress tiếp theo
        ll current_pos = current_reach; 
        
        // Chúng ta có thể thêm tối đa bao nhiêu trạm?
        // Thực tế chỉ cần tính tối đa K lần hoặc đến khi phủ hết đoạn, vì ta chỉ lấy top K-M
        int added_count = 0;
        
        while (current_pos < next_stop - 1 && added_count < K) {
            // Giả sử đặt trạm Semiexpress tại (current_pos + 1)
            // Thời gian để đến trạm này bằng:
            // Tốc hành đến start + Bán tốc hành từ start đến (current_pos + 1)
            ll next_semiexpress_pos = current_pos + 1;
            ll time_via_semi = (start - 1) * B + (next_semiexpress_pos - start) * C;
            
            if (time_via_semi > T) break; // Quá giờ, không thể đặt trạm ở đây
            
            // Từ trạm Semiexpress mới này, đi tiếp bằng Tàu thường được bao xa?
            ll rem = T - time_via_semi;
            ll d_loc = rem / A;
            
            ll new_reach = min(next_stop - 1, next_semiexpress_pos + d_loc);
            
            // Số lượng ga MỚI cứu được
            ll gain = new_reach - current_pos;
            if (gain <= 0) break; // Không cứu thêm được gì
            
            gains.push_back(gain);
            
            // Cập nhật vị trí hiện tại
            current_pos = new_reach;
            added_count++;
        }
    }

    // Xử lý riêng ga cuối cùng S[M] (tức là ga N)
    // Đoạn vòng lặp trên chỉ tính đến S[i+1] - 1.
    if ((S[M-1] - 1) * B <= T) {
        total_stations++;
    }

    // --- PHẦN 3: Chọn K - M đoạn có lợi nhất ---
    sort(gains.rbegin(), gains.rend()); // Sắp xếp giảm dần
    
    int slots_available = K - M;
    for (int i = 0; i < gains.size() && i < slots_available; i++) {
        total_stations += gains[i];
    }

    // Kết quả là tổng số ga đi được trừ đi ga xuất phát (ga 1)
    cout << total_stations - 1 << endl;

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...