結果

問題 No.919 You Are A Project Manager
コンテスト
ユーザー lam6er
提出日時 2025-03-31 18:00:21
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,050 bytes
コンパイル時間 343 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 95,960 KB
最終ジャッジ日時 2025-03-31 18:01:16
合計ジャッジ時間 9,192 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    N, *rest = list(map(int, sys.stdin.read().split()))
    A = rest[:N]
    max_total = 0
    
    for K in range(1, N+1):
        if K > N:
            continue
        # Compute prefix_left: sum of medians for left segments
        prefix_left = [0]
        for i in range(1, (N // K) + 1):
            start = (i-1) * K
            end = start + K - 1
            if end >= N:
                break
            sub = A[start:end+1]
            sub_sorted = sorted(sub)
            if K % 2 == 0:
                median = sub_sorted[K//2 - 1]
            else:
                median = sub_sorted[(K-1)//2]
            prefix_left.append(prefix_left[-1] + median)
        
        # Compute prefix_right: sum of medians for right segments
        prefix_right = [0]
        for j in range(1, (N // K) + 1):
            end = N - K*(j-1) - 1
            start = end - K + 1
            if start < 0:
                break
            sub = A[start:end+1]
            sub_sorted = sorted(sub)
            if K % 2 == 0:
                median = sub_sorted[K//2 - 1]
            else:
                median = sub_sorted[(K-1)//2]
            prefix_right.append(prefix_right[-1] + median)
        
        # Compute right_max array
        right_max = [0] * len(prefix_right)
        current_max = 0
        for j in range(len(prefix_right)):
            current_max = max(current_max, prefix_right[j])
            right_max[j] = current_max
        
        # Find the best a and b
        best_sum = 0
        for a in range(len(prefix_left)):
            remaining = N - a * K
            if remaining < 0:
                continue
            b_max = remaining // K
            b_max = min(b_max, len(prefix_right)-1)
            current_sum = prefix_left[a] + right_max[b_max]
            if current_sum > best_sum:
                best_sum = current_sum
        
        total = best_sum * K
        if total > max_total:
            max_total = total
    
    print(max_total)

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