結果
問題 |
No.919 You Are A Project Manager
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()