結果

問題 No.1739 Princess vs. Dragoness (& AoE)
コンテスト
ユーザー moharan627
提出日時 2021-11-12 22:55:11
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 606 ms / 3,000 ms
コード長 1,654 bytes
コンパイル時間 253 ms
コンパイル使用メモリ 82,460 KB
実行使用メモリ 112,856 KB
最終ジャッジ日時 2024-11-25 20:53:06
合計ジャッジ時間 11,082 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
#sys.setrecursionlimit(10 ** 6)
INF = float('inf')
#10**20,2**63に変えるのもあり
MOD = 10**9 + 7
MOD2 = 998244353
from collections import defaultdict
def II(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LC(): return list(input())
def IC(): return [int(c) for c in input()]
def MI(): return map(int, sys.stdin.readline().split())
N,A,B,X,Y = MI()
H =LI()
def is_ok(K):
    # 条件を満たすかどうか？問題ごとに定義
    a,b,x,y = A,B,X,Y
    HP = [0]*N
    for n in range(N):
        HP[n] = H[n]-K
    for n in range(N):
        if(HP[n]<=0):
            continue
        atk = HP[n]//x
        at = min(atk,a)
        HP[n] -=at*x
        a-=at
    if 0<a:
        HP.sort(reverse=True)
        for n in range(min(N,a)):
            HP[n] = 0
    SUM = 0
    for h in HP:
        if h<=0:
            continue
        else:
            SUM += h
    return SUM <= b*y
def meguru_bisect(ng, ok):
    """
    この条件は、問題に基づくやつじゃなくてもOK
    条件の付け方は、ngとokの広げ方をどのようにするかで決まってくる。
    （目的値）～正の無限 が条件を満たす場合
    ng…条件を満たさない値の範囲での最大値
    ok…条件を満たす値の範囲での最小値
    ng < ok
    is_ok == Trueの場合、探索範囲が左半分へ
    is_ok == Falseの場合、探索範囲が右半分へ
    """
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok
print(meguru_bisect(-1,10**9))
0