結果

問題 No.2078 魔抜けなパープル
ユーザー taiga0629kyoprotaiga0629kyopro
提出日時 2022-09-08 00:42:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 58 ms / 2,000 ms
コード長 2,055 bytes
コンパイル時間 1,401 ms
コンパイル使用メモリ 81,880 KB
実行使用メモリ 67,896 KB
最終ジャッジ日時 2024-11-25 16:10:47
合計ジャッジ時間 1,502 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 47 ms
56,968 KB
testcase_01 AC 57 ms
67,896 KB
testcase_02 AC 55 ms
66,320 KB
testcase_03 AC 56 ms
67,456 KB
testcase_04 AC 54 ms
66,596 KB
testcase_05 AC 53 ms
66,532 KB
testcase_06 AC 58 ms
67,036 KB
testcase_07 AC 52 ms
64,920 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(sol3(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