結果

問題 No.919 You Are A Project Manager
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 20:39:45
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,859 bytes
コンパイル時間 305 ms
コンパイル使用メモリ 82,660 KB
実行使用メモリ 98,168 KB
最終ジャッジ日時 2025-06-12 20:39:55
合計ジャッジ時間 8,797 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 54
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    A = list(map(int, input[1:N+1]))
    
    max_total = 0
    
    for K in range(1, N+1):
        m = N // K
        if m == 0:
            continue
        
        # Compute prefix_teams
        prefix = [0] * (m + 1)
        for x in range(1, m + 1):
            start = (x - 1) * K
            end = start + K
            team = A[start:end]
            team_sorted = sorted(team)
            if K % 2 == 0:
                median = team_sorted[K//2 - 1]
            else:
                median = team_sorted[K//2]
            prefix[x] = prefix[x - 1] + K * median
        
        # Compute suffix_teams
        suffix = [0] * (m + 1)
        for y in range(1, m + 1):
            start = N - y * K
            end = start + K
            team = A[start:end]
            team_sorted = sorted(team)
            if K % 2 == 0:
                median = team_sorted[K//2 - 1]
            else:
                median = team_sorted[K//2]
            suffix[y] = suffix[y - 1] + K * median
        
        # Compute max_suffix array
        max_suffix = [0] * (m + 1)
        current_max = 0
        for y in range(m + 1):
            if suffix[y] > current_max:
                current_max = suffix[y]
            max_suffix[y] = current_max
        
        # Find the maximum sum for this K
        current_max_sum = 0
        for x in range(len(prefix)):
            remaining = m - x
            if remaining < 0:
                continue
            y_max = min(remaining, m)
            sum_xy = prefix[x] + max_suffix[y_max]
            if sum_xy > current_max_sum:
                current_max_sum = sum_xy
        
        if current_max_sum > max_total:
            max_total = current_max_sum
    
    print(max_total)

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