結果

問題 No.1708 Quality of Contest
ユーザー lam6er
提出日時 2025-03-20 20:58:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 953 ms / 2,000 ms
コード長 3,071 bytes
コンパイル時間 155 ms
コンパイル使用メモリ 82,704 KB
実行使用メモリ 181,568 KB
最終ジャッジ日時 2025-03-20 20:58:35
合計ジャッジ時間 17,410 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    n = int(data[idx])
    m = int(data[idx+1])
    x = int(data[idx+2])
    idx +=3
    problems = []
    for _ in range(n):
        a = int(data[idx])
        b = int(data[idx+1])
        problems.append( (a, b) )
        idx +=2
    k = int(data[idx])
    idx +=1
    c = list(map(int, data[idx:idx+k]))
    idx +=k

    # Compute cnt_j for j in 1..n
    c_sorted = sorted(c)
    cnt = [0]*(n+2)  # cnt[j] is for 1-based j
    for j in range(1, n+1):
        cnt_j = k - bisect.bisect_left(c_sorted, j)
        cnt[j] = cnt_j

    # Build genre_dict: { genre: sorted list of A in descending order }
    genre_dict = {}
    for a, b in problems:
        if b not in genre_dict:
            genre_dict[b] = []
        genre_dict[b].append(a)
    # Sort each genre's list in descending order
    for b in genre_dict:
        genre_dict[b].sort(reverse=True)
    # current_index for each genre, tracks next available problem index
    current_index = {b:0 for b in genre_dict}

    # Prepare the unused heap (max-heap by a_i +x)
    unused_heap = []
    for b in genre_dict:
        a_list = genre_dict[b]
        if not a_list:
            continue
        a_max = a_list[0]
        heapq.heappush(unused_heap, ( - (a_max + x), b ))  # max-heap simulation

    # Prepare used heap (max-heap by a_i), starts empty
    used_heap = []

    sum_quality = 0
    sum_x = 0

    for j in range(1, n+1):
        current_cnt = cnt[j]
        if current_cnt == 0:
            continue  # no participants, skip

        # Check candidates from unused and used
        candidate_unused = -float('inf')
        if unused_heap:
            candidate_unused_val = -unused_heap[0][0]
            candidate_unused = candidate_unused_val * current_cnt

        candidate_used = -float('inf')
        if used_heap:
            candidate_used_val = -used_heap[0][0]
            candidate_used = candidate_used_val * current_cnt

        if candidate_unused >= candidate_used:
            # Take from unused heap
            val, b = heapq.heappop(unused_heap)
            a_plus_x = -val
            a = a_plus_x - x
            sum_quality += a * current_cnt
            sum_x += x * current_cnt
            # Move current_index forward
            current_index[b] += 1
            # Push remaining to used if any
            if current_index[b] < len(genre_dict[b]):
                next_a = genre_dict[b][current_index[b]]
                heapq.heappush(used_heap, (-next_a, b))
        else:
            # Take from used heap
            val, b = heapq.heappop(used_heap)
            a = -val
            sum_quality += a * current_cnt
            # Move current_index forward
            current_index[b] +=1
            if current_index[b] < len(genre_dict[b]):
                next_a = genre_dict[b][current_index[b]]
                heapq.heappush(used_heap, (-next_a, b))

    total = sum_quality + sum_x
    print(total)

if __name__ == "__main__":
    main()
0