結果
問題 | 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;