結果
問題 | No.1739 Princess vs. Dragoness (& AoE) |
ユーザー |
👑 ![]() |
提出日時 | 2021-11-12 21:34:15 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 298 ms / 3,000 ms |
コード長 | 1,194 bytes |
コンパイル時間 | 2,472 ms |
コンパイル使用メモリ | 109,760 KB |
最終ジャッジ日時 | 2025-01-25 15:55:50 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 40 |
ソースコード
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; using i32 = int32_t; using u32 = uint32_t; using i64 = int64_t; using u64 = uint64_t; #define rep(i,n) for(int i=0; i<(n); i++) int main(){ i64 N, A, B, X, Y; cin >> N >> A >> B >> X >> Y; vector<i64> H(N); for (auto& h : H) cin >> h; auto solver = [&](i64 k)->bool { i64 a = A; vector<i64> newH; for (auto& h : H) { i64 hh = max<i64>(0, h - k); i64 adec = min<i64>(a, hh / X); newH.push_back(hh - adec * X); a -= adec; } sort(newH.begin(), newH.end()); i64 sumH = 0; for (auto& h : newH) sumH += h; if (a >= N) return true; for (int i = 0; i < a; i++) { sumH -= newH.back(); newH.pop_back(); } return sumH <= B * Y; }; i64 l = -1, r = 1001001001; while (r - l > 1) { i64 m = (l + r) / 2; if (solver(m)) r = m; else l = m; } cout << r << endl; return 0; } struct ios_do_not_sync { ios_do_not_sync() { ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;