結果
問題 | No.2548 Problem Selection |
ユーザー |
|
提出日時 | 2023-11-25 14:06:45 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 226 ms / 2,000 ms |
コード長 | 4,986 bytes |
コンパイル時間 | 535 ms |
コンパイル使用メモリ | 82,340 KB |
実行使用メモリ | 106,108 KB |
最終ジャッジ日時 | 2024-09-26 10:39:12 |
合計ジャッジ時間 | 6,804 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
from random import getrandbits, randrangefrom string import ascii_lowercase, ascii_uppercaseimport sysfrom math import ceil, floor, sqrt, pi, factorial, gcd, log, log10, log2, inf, cos, sinfrom copy import deepcopy, copyfrom collections import Counter, deque, defaultdictfrom heapq import heapify, heappop, heappushfrom itertools import (accumulate,product,combinations,combinations_with_replacement,permutations,)from bisect import bisect, bisect_left, bisect_rightfrom functools import lru_cache, reducefrom decimal import Decimal, getcontextfrom typing import List, Tuple, Optionalinf = float("inf")def ceil_div(a, b):return (a + b - 1) // bdef isqrt(num):res = int(sqrt(num))while res * res > num:res -= 1while (res + 1) * (res + 1) <= num:res += 1return resdef int1(s):return int(s) - 1from types import GeneratorTypedef bootstrap(f, stack=[]):def wrapped(*args, **kwargs):if stack:return f(*args, **kwargs)else:to = f(*args, **kwargs)while True:if type(to) is GeneratorType:stack.append(to)to = next(to)else:stack.pop()if not stack:breakto = stack[-1].send(to)return toreturn wrappedimport sysimport osinput = lambda: sys.stdin.readline().rstrip("\r\n")print = lambda *args, end="\n", sep=" ": sys.stdout.write(sep.join(map(str, args)) + end)def II():return int(input())def MII(base=0):return map(lambda s: int(s) - base, input().split())def LII(base=0):return list(MII(base))def NA():n = II()a = LII()return n, adef read_graph(n, m, base=0, directed=False, return_edges=False):g = [[] for _ in range(n)]edges = []for _ in range(m):a, b = MII(base)if return_edges:edges.append((a, b))g[a].append(b)if not directed:g[b].append(a)if return_edges:return g, edgesreturn gdef read_graph_with_weight(n, m, base=0, directed=False, return_edges=False):g = [[] for _ in range(n)]edges = []for _ in range(m):a, b, w = MII()a, b = a - base, b - baseif return_edges:edges.append((a, b, w))g[a].append((b, w))if not directed:g[b].append((a, w))if return_edges:return g, edgesreturn gdef iterate_tokens():for line in sys.stdin:for word in line.split():yield wordtokens = Nonedef NI():global tokensif tokens is None:tokens = iterate_tokens()return int(next(tokens))def LNI(n):return [NI() for _ in range(n)]def yes(res):print("Yes" if res else "No")def YES(res):print("YES" if res else "NO")def pairwise(a):n = len(a)for i in range(n - 1):yield a[i], a[i + 1]def factorial(n):return reduce(lambda x, y: x * y, range(1, n + 1))def cmin(dp, i, x):if x < dp[i]:dp[i] = xdef cmax(dp, i, x):if x > dp[i]:dp[i] = xdef alp_a_to_i(s):return ord(s) - ord("a")def alp_A_to_i(s):return ord(s) - ord("A")def alp_i_to_a(i):return chr(ord("a") + i)def alp_i_to_A(i):return chr(ord("A") + i)d4 = [(1, 0), (0, 1), (-1, 0), (0, -1)]d8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]def ranges(n, m):return ((i, j) for i in range(n) for j in range(m))def valid(i, j, n, m):return 0 <= i < n and 0 <= j < mdef ninj(i, j, n, m):return [(i + di, j + dj) for di, dj in d4 if valid(i + di, j + dj, n, m)]def gen(x, *args):if len(args) == 1:return [x] * args[0]if len(args) == 2:return [[x] * args[1] for _ in [0] * args[0]]if len(args) == 3:return [[[x] * args[2] for _ in [0] * args[1]] for _ in [0] * args[0]]if len(args) == 4:return [[[[x] * args[3] for _ in [0] * args[2]] for _ in [0] * args[1]]for _ in [0] * args[0]]list2d = lambda a, b, v: [[v] * b for _ in range(a)]list3d = lambda a, b, c, v: [[[v] * c for _ in range(b)] for _ in range(a)]class Debug:def __init__(self, debug=False):self.debug = debugcur_path = os.path.dirname(os.path.abspath(__file__))self.local = os.path.exists(cur_path + "/.cph")def get_ic(self):if self.debug and self.local:from icecream import icreturn icelse:return lambda *args, **kwargs: ...ic = Debug(1).get_ic()n, m = MII()a = LII()a.sort()s = sum((y - x) ** 2 for x, y in pairwise(a[:m]))res = sfor i in range(m, n):s += (a[i] - a[i - 1]) ** 2s -= (a[i - m + 1] - a[i - m]) ** 2res = min(res, s)print(res)