제출 #1269714

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269714		seoul_korea	Candies (JOI18_candies)	C++17	0 / 100	1 ms	576 KiB

candies

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

// Định nghĩa kích thước tối đa cho N. Vì có thể tạo thêm virtual candies,
// kích thước mảng cần lớn hơn N. Tối đa N + ceil(N/2) phần tử.
// N_MAX_REAL_CANDIES = 200,000. => 200,000 + 100,000 = 300,000.
// Dùng 2 * N_MAX_REAL_CANDIES để an toàn.
const int N_MAX_REAL_CANDIES = 200005; // N + 5 for safety buffer
const int MAX_TOTAL_CANDIES = N_MAX_REAL_CANDIES * 2; // Đủ cho real và virtual candies

long long A[MAX_TOTAL_CANDIES]; // Mảng lưu giá trị ngon miệng của kẹo (thực và ảo)
int L[MAX_TOTAL_CANDIES], R[MAX_TOTAL_CANDIES]; // Mảng danh sách liên kết đôi
bool deleted[MAX_TOTAL_CANDIES]; // Mảng đánh dấu kẹo đã bị xóa (không hợp lệ)

// Cặp (giá_trị, chỉ_số) để lưu trong priority_queue.
// std::priority_queue mặc định là max-heap (lấy phần tử lớn nhất).
using Candy = std::pair<long long, int>;

// Mảng lưu trữ các câu trả lời cho mỗi j (số lượng kẹo được ăn)
long long answers[N_MAX_REAL_CANDIES / 2 + 5];

int main() {
    // Tối ưu hóa I/O để đọc/ghi nhanh hơn
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int N; // Số lượng viên kẹo ban đầu
    std::cin >> N;

    // Hàng đợi ưu tiên để lưu trữ các viên kẹo tiềm năng (giá trị, chỉ số)
    std::priority_queue<Candy> pq;

    // Khởi tạo các viên kẹo thực tế và danh sách liên kết đôi
    for (int i = 0; i < N; ++i) {
        std::cin >> A[i]; // Đọc giá trị ngon miệng của kẹo thứ i
        L[i] = i - 1;     // Chỉ số kẹo bên trái
        R[i] = i + 1;     // Chỉ số kẹo bên phải
        deleted[i] = false; // Ban đầu chưa có kẹo nào bị xóa
        pq.push({A[i], i}); // Thêm kẹo vào hàng đợi ưu tiên
    }
    // Cập nhật phần tử cuối cùng của danh sách liên kết đôi
    if (N > 0) {
        R[N - 1] = -1;
    }

    long long current_total_sum = 0; // Tổng giá trị ngon miệng hiện tại
    int candies_eaten_count = 0;    // Số lượng kẹo đã ăn
    
    // Bộ đếm ID cho các viên kẹo ảo, bắt đầu từ N
    // Các ID này sẽ không trùng với ID của các viên kẹo thực (0 đến N-1)
    int virtual_candy_id_counter = N; 

    // Số lượng kẹo tối đa có thể ăn là ceil(N/2)
    // Sử dụng phép chia số nguyên (N + 1) / 2 để tính ceil(N/2) cho số nguyên dương
    int max_candies_to_eat = (N + 1) / 2;

    // Vòng lặp chính: chọn kẹo cho đến khi đạt số lượng tối đa hoặc PQ trống
    while (candies_eaten_count < max_candies_to_eat && !pq.empty()) {
        Candy top_candy = pq.top(); // Lấy viên kẹo có giá trị cao nhất
        pq.pop(); // Xóa khỏi PQ

        long long val = top_candy.first; // Giá trị của viên kẹo
        int idx = top_candy.second;      // Chỉ số của viên kẹo

        if (deleted[idx]) { // Nếu viên kẹo này đã bị xử lý (do bị chọn hoặc bị loại bỏ bởi hàng xóm)
            continue;       // Bỏ qua và lấy viên kẹo tiếp theo
        }

        // Chọn viên kẹo này
        current_total_sum += val;
        candies_eaten_count++;
        answers[candies_eaten_count] = current_total_sum; // Lưu kết quả cho j viên kẹo

        // Đánh dấu viên kẹo hiện tại là đã bị xóa (vì đã chọn)
        deleted[idx] = true;

        // Lấy hàng xóm của viên kẹo vừa chọn
        int left_neighbor = L[idx];
        int right_neighbor = R[idx];

        // Đánh dấu các viên kẹo lân cận là đã bị xóa (vì không thể chọn chúng)
        if (left_neighbor != -1) {
            deleted[left_neighbor] = true;
        }
        if (right_neighbor != -1) {
            deleted[right_neighbor] = true;
        }

        // Tạo một viên kẹo ảo mới. Giá trị của nó là tổng của hai hàng xóm
        // trừ đi giá trị của viên kẹo hiện tại đã chọn.
        // Đây là "sự hối tiếc" nếu chúng ta đã chọn hàng xóm thay vì kẹo hiện tại.
        long long new_val = 0;
        if (left_neighbor != -1) {
            new_val += A[left_neighbor];
        }
        if (right_neighbor != -1) {
            new_val += A[right_neighbor];
        }
        new_val -= A[idx]; // Trừ đi giá trị của kẹo đã chọn để tính net change

        int new_id = virtual_candy_id_counter++; // Gán ID mới cho kẹo ảo
        A[new_id] = new_val; // Lưu giá trị của kẹo ảo

        // Cập nhật con trỏ của danh sách liên kết đôi cho viên kẹo ảo mới
        // Viên kẹo ảo sẽ nối các hàng xóm cũ của L[left_neighbor] và R[right_neighbor]
        int prev_of_left = (left_neighbor != -1 ? L[left_neighbor] : -1);
        int next_of_right = (right_neighbor != -1 ? R[right_neighbor] : -1);

        L[new_id] = prev_of_left;
        R[new_id] = next_of_right;

        // Cập nhật lại con trỏ của các hàng xóm xa hơn để chúng trỏ đến viên kẹo ảo mới
        if (prev_of_left != -1) {
            R[prev_of_left] = new_id;
        }
        if (next_of_right != -1) {
            L[next_of_right] = new_id;
        }

        // Thêm viên kẹo ảo mới vào hàng đợi ưu tiên
        pq.push({new_val, new_id});
    }

    // In ra kết quả cho mỗi j
    for (int j = 1; j <= max_candies_to_eat; ++j) {
        std::cout << answers[j] << "\n";
    }

    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92