結果

問題 No.1912 Get together 2
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:09:57
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,290 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 130,120 KB
最終ジャッジ日時 2025-06-12 13:13:19
合計ジャッジ時間 21,146 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 4 WA * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, m = map(int, input().split())
v = list(map(int, input().split()))
s = [input().strip() for _ in range(n)]

sum_potential = [0] * m
allowed_boxes = [[] for _ in range(n)]

for i in range(n):
    current_s = s[i]
    boxes = []
    for j in range(m):
        if current_s[j] == 'o':
            boxes.append(j)
            sum_potential[j] += v[i]
    allowed_boxes[i] = boxes

# Create a list of (v, allowed_boxes) sorted by descending v
slimes = sorted(zip(v, allowed_boxes), key=lambda x: (-x[0], x[1]))

sum_boxes = [0] * m

for val, boxes in slimes:
    if not boxes:
        continue  # As per problem statement, each slime has at least one 'o'
    # Find max current sum among allowed boxes
    max_sum = max(sum_boxes[j] for j in boxes)
    candidates = [j for j in boxes if sum_boxes[j] == max_sum]
    # Select the candidate with the highest sum_potential
    selected_j = candidates[0]
    max_p = sum_potential[selected_j]
    for j in candidates[1:]:
        if sum_potential[j] > max_p:
            max_p = sum_potential[j]
            selected_j = j
    sum_boxes[selected_j] += val
    # Update sum_potential for all allowed boxes of this slime
    for j in boxes:
        sum_potential[j] -= val

# Calculate the result
result = sum(x * x for x in sum_boxes)
print(result)
0