結果

問題 No.2095 High Rise
ユーザー lam6er
提出日時 2025-03-20 20:19:27
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,246 bytes
コンパイル時間 277 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 175,872 KB
最終ジャッジ日時 2025-03-20 20:20:25
合計ジャッジ時間 5,305 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx])
    idx += 1
    M = int(input[idx])
    idx += 1
    if N == 1:
        print(0)
        return
    
    A = []
    for _ in range(N):
        row = list(map(int, input[idx:idx+M]))
        idx += M
        A.append(row)
    
    # Compute sum_Aj for each column (covers all floors)
    sum_Aj = []
    for j in range(M):
        total = sum(A[i][j] for i in range(N))
        sum_Aj.append(total)
    ans_candidate1 = min(sum_Aj)
    
    # Precompute left and right for each column
    left = []
    right = []
    for j in range(M):
        # Compute prefix sums (left[i] is sum from floor 1 to i+1 (0-based))
        prefix = [0] * (N+1)
        for i in range(N):
            prefix[i+1] = prefix[i] + A[i][j]
        left_j = prefix[1:]  # left_j[0] is A[0], left_j[i] is sum from 0 to i
        left.append(left_j)
        
        # Compute suffix sums (right[i] is sum from floor i (0-based) to N-1
        suffix = [0] * (N+1)
        for i in range(N-1, -1, -1):
            suffix[i] = suffix[i+1] + A[i][j]
        right_j = [0] * N
        for i in range(N):
            right_j[i] = suffix[i]
        right.append(right_j)
    
    # Compute left_min and right_min for each floor (0-based?)
    left_min = [float('inf')] * (N)
    right_min = [float('inf')] * (N)
    
    for j in range(M):
        for i in range(N):
            if left[j][i] < left_min[i]:
                left_min[i] = left[j][i]
            if right[j][i] < right_min[i]:
                right_min[i] = right[j][i]
    
    ans_candidate2 = float('inf')
    for i in range(N):
        # i is 0-based, corresponds to floor 1-based i+1
        # left_min[i] is sum from floor 1 to i+1 (if 0-based)
        # Need to check if i+1 covers at least some part, and i+1 < N
        current_left = left_min[i]
        current_right = right_min[i] if i < N-1 else 0  # if i == N-1, there's nothing to the right
        if i < N-1:
            total = current_left + current_right
            if total < ans_candidate2:
                ans_candidate2 = total
    
    answer = min(ans_candidate1, ans_candidate2)
    print(answer)

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