結果
問題 | No.2548 Problem Selection |
ユーザー |
![]() |
提出日時 | 2023-11-21 17:20:09 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 96 ms / 2,000 ms |
コード長 | 913 bytes |
コンパイル時間 | 201 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 94,848 KB |
最終ジャッジ日時 | 2024-09-26 07:15:49 |
合計ジャッジ時間 | 3,768 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
def solve(n, m, a_list):# (a + b)^2 >= a^2 + b^2なので、# 難易度の小さい順に並べたとき、間を飛ばす理由がないif m == 1:return 0d_list = []a_list_s = list(sorted(a_list))for i in range(n - 1):d_list.append((a_list_s[i + 1] - a_list_s[i]) ** 2)r = sum(d_list[:(m - 1)])res = rfor i in range(m - 1, n - 1):r += d_list[i]r -= d_list[i - (m - 1)]res = min(res, r)return resdef main():n, m = map(int, input().split())a_list = list(map(int, input().split()))res = solve(n, m, a_list)print(res)def test():assert solve(5, 3, [7, 6, 2, 9, 5]) == 2assert solve(10, 5, [227930076, 836334727, 108597970, 656892815, 455743732, 901045388, 302006162, 256603330, 228958951, 169578258]) == 6231622091586614if __name__ == "__main__":test()main()