結果

問題 No.2078 魔抜けなパープル
ユーザー taiga0629kyoprotaiga0629kyopro
提出日時 2022-09-09 17:13:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 679 ms / 2,000 ms
コード長 2,052 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 82,192 KB
実行使用メモリ 140,048 KB
最終ジャッジ日時 2024-05-04 07:00:54
合計ジャッジ時間 3,970 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 114 ms
79,720 KB
testcase_01 AC 462 ms
116,480 KB
testcase_02 AC 371 ms
104,704 KB
testcase_03 AC 424 ms
111,648 KB
testcase_04 AC 353 ms
101,768 KB
testcase_05 AC 350 ms
102,092 KB
testcase_06 AC 679 ms
140,048 KB
testcase_07 AC 279 ms
103,340 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 


#########################################
from collections import deque
class Convex_Hull_Trick():

    #https://tjkendev.github.io/procon-library/python/convex_hull_trick/deque.html
    #追加する傾きが単調減少かつqueryのxが単調増加
    #単調性なしが良いならこちらへ(queryのxは先読み) https://judge.yosupo.jp/submission/30579

    def __init__(self):
        self.deq=deque()
    def check(self,f1, f2, f3):
        return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])
    def f(self,f1, x):
        return f1[0] * x + f1[1]

    # add f_i(x) = a*x + b
    def add_line(self,a, b):
        f1 = (a, b)
        while len(self.deq) >= 2 and self.check(self.deq[-2], self.deq[-1], f1):
            self.deq.pop()
        self.deq.append(f1)

    # min f_i(x)
    def query(self,x):
        while len(self.deq) >= 2 and self.f(self.deq[0], x) >= self.f(self.deq[1], x):
            self.deq.popleft()
        return self.f(self.deq[0], x)

##################################







def sol1(X,A):
    #O(A)
    ans = 2 ** 63
    for k in range(1, A + 1):
        cnt1 = k - A % k
        cnt2 = A % k
        res = cnt1 * ((A // k)**2) + cnt2 * ((A // k + 1)**2) + X * k
        ans = min(ans, res)
    return ans

def sol2(X,A):
    #O(A)
    dp=[2**63]*(A+1)
    dp[0]=0
    cht=Convex_Hull_Trick()
    cht.add_line(0,0)
    for i in range(1,A+1):
        dp[i]=cht.query(i)+i**2+X
        cht.add_line(-2*i,dp[i]+i**2)
    return dp[A]

def sol3(X,A):
    #O(√A)
    R=A
    ans=2**63
    while R:
        q=A//R
        L=A//(q+1)+1
        def f(k):
            return k*(q**2)+(A-q*k)*(2*q+1)+X*k
        ans=min(ans,f(L),f(R))
        R=L-1
    return ans


T=int(input())
for iii in range(T):
    X,A=map(int,input().split())
    print(sol2(X,A))


from random import randrange as rd
cnt=0

while 0:
    cnt+=1
    print(cnt)
    X=rd(100)
    A=rd(1,10**4)
    ans1=sol1(X,A)
    ans2=sol2(X,A)
    ans3=sol3(X,A)
    if not(ans1==ans2==ans3):
        print(X,A)
        exit()
0