結果
問題 | No.1739 Princess vs. Dragoness (& AoE) |
ユーザー | okuraofvegetabl |
提出日時 | 2021-11-12 21:51:37 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 853 ms / 3,000 ms |
コード長 | 4,401 bytes |
コンパイル時間 | 2,351 ms |
コンパイル使用メモリ | 205,468 KB |
実行使用メモリ | 6,640 KB |
最終ジャッジ日時 | 2023-08-17 01:04:03 |
合計ジャッジ時間 | 20,735 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 4 ms
4,376 KB |
testcase_04 | AC | 758 ms
6,560 KB |
testcase_05 | AC | 841 ms
6,484 KB |
testcase_06 | AC | 304 ms
6,424 KB |
testcase_07 | AC | 5 ms
4,376 KB |
testcase_08 | AC | 242 ms
5,236 KB |
testcase_09 | AC | 388 ms
6,040 KB |
testcase_10 | AC | 393 ms
4,452 KB |
testcase_11 | AC | 295 ms
4,380 KB |
testcase_12 | AC | 28 ms
4,376 KB |
testcase_13 | AC | 479 ms
5,124 KB |
testcase_14 | AC | 562 ms
5,996 KB |
testcase_15 | AC | 638 ms
6,488 KB |
testcase_16 | AC | 403 ms
4,380 KB |
testcase_17 | AC | 312 ms
4,692 KB |
testcase_18 | AC | 486 ms
4,688 KB |
testcase_19 | AC | 234 ms
4,792 KB |
testcase_20 | AC | 98 ms
4,380 KB |
testcase_21 | AC | 443 ms
5,992 KB |
testcase_22 | AC | 577 ms
6,524 KB |
testcase_23 | AC | 832 ms
6,412 KB |
testcase_24 | AC | 840 ms
6,408 KB |
testcase_25 | AC | 853 ms
6,492 KB |
testcase_26 | AC | 830 ms
6,464 KB |
testcase_27 | AC | 842 ms
6,408 KB |
testcase_28 | AC | 806 ms
6,640 KB |
testcase_29 | AC | 844 ms
6,468 KB |
testcase_30 | AC | 838 ms
6,512 KB |
testcase_31 | AC | 806 ms
6,532 KB |
testcase_32 | AC | 818 ms
6,468 KB |
testcase_33 | AC | 2 ms
4,380 KB |
testcase_34 | AC | 2 ms
4,376 KB |
testcase_35 | AC | 3 ms
4,376 KB |
testcase_36 | AC | 2 ms
4,376 KB |
testcase_37 | AC | 2 ms
4,376 KB |
testcase_38 | AC | 2 ms
4,380 KB |
testcase_39 | AC | 4 ms
4,380 KB |
testcase_40 | AC | 2 ms
4,380 KB |
testcase_41 | AC | 3 ms
4,380 KB |
testcase_42 | AC | 2 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define eps 1e-9 #define INF 2000000000 // 2e9 #define LLINF 2000000000000000000ll // 2e18 (llmax:9e18) #define all(x) (x).begin(), (x).end() #define sq(x) ((x) * (x)) #define rep(i, x) for (int i = 0; i < (int)(x); i++) #define drep(i, x) for (int i = ((int)(x)-1); i >= 0; i--) #define popcount __builtin_popcount #define next __next #define prev __prev #ifndef LOCAL #define dmp(...) ; #else #define dmp(...) \ cerr << "[ " << #__VA_ARGS__ << " ] : " << dump_str(__VA_ARGS__) << endl #endif // ---------------- Utility ------------------ template <class T> bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template <class T> bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } template <class T> using MaxHeap = priority_queue<T>; template <class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>; template <class T> vector<T> vect(int len, T elem) { return vector<T>(len, elem); } // ----------------- Input ------------------- template <class T, class U> istream &operator>>(istream &is, pair<T, U> &p) { return is >> p.first >> p.second; } template <class T> istream &operator>>(istream &is, vector<T> &vec) { for (int i = 0; i < vec.size(); i++) is >> vec[i]; return is; } // ----------------- Output ------------------ template <class T, class U> ostream &operator<<(ostream &os, const pair<T, U> &p) { return os << p.first << ',' << p.second; } template <class T> ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &e : v) os << e << " "; return os; } template <class T> ostream &operator<<(ostream &os, const deque<T> &d) { for (const T &e : d) os << e << " "; return os; } template <class T> ostream &operator<<(ostream &os, const set<T> &s) { os << "{ "; for (const T &e : s) os << e << " "; return os << "}"; } template <class T, class U> ostream &operator<<(ostream &os, const map<T, U> &m) { os << "{ "; for (const auto &[key, val] : m) os << "( " << key << " -> " << val << " ) "; return os << "}"; } template <class TupleTy, size_t... I> void dump_tuple(ostream &os, const TupleTy t, std::index_sequence<I...>) { (..., (os << (I == 0 ? "" : ",") << std::get<I>(t))); } template <class... Args> ostream &operator<<(ostream &os, const tuple<Args...> &t) { os << "("; dump_tuple(os, t, std::make_index_sequence<sizeof...(Args)>()); return os << ")"; } void dump_str_rec(ostringstream &) {} template <class Head, class... Tail> void dump_str_rec(ostringstream &oss, Head &&head, Tail &&... tail) { oss << ", " << head; dump_str_rec(oss, forward<Tail>(tail)...); } template <class T, class... U> string dump_str(T &&arg, U &&... args) { ostringstream oss; oss << arg; dump_str_rec(oss, forward<U>(args)...); return oss.str(); } // --------------- Fast I/O ------------------ void fastio() { cin.tie(0); ios::sync_with_stdio(0); cout << fixed << setprecision(20); } // ------------------ ACL -------------------- // #include <atcoder/modint> // constexpr int MOD = 998244353; // constexpr int MOD = 1000000007; // using mint = atcoder::static_modint<MOD>; // ostream &operator<<(ostream &os, const mint &v) { // return os << v.val(); // } // ------------ End of template -------------- #define endl "\n" using ll = long long; using pii = pair<int, int>; const bool multitest = false; bool check(ll K, int N, int A, int B, ll X, ll Y, vector<ll> H) { for (int i = 0; i < N; i++) H[i] -= K; MaxHeap<ll> q; for (int i = 0; i < N; i++) q.push(H[i]); for (int i = 0; i < A; i++) { int a = q.top(); q.pop(); q.push(a - X); } ll sum = 0ll; while (!q.empty()) { sum += max(0ll, q.top()); q.pop(); } if (sum <= (ll)B * Y) return true; return false; } void solve() { int N, A, B; ll X, Y; cin >> N >> A >> B >> X >> Y; vector<ll> H(N); cin >> H; ll l = -1ll, r = 1000000000ll; while (r - l > 1ll) { ll mid = (l + r) / 2ll; if (check(mid, N, A, B, X, Y, H)) r = mid; else l = mid; } cout << r << endl; return; } int main() { fastio(); if (!multitest) { solve(); } else { cerr << "[Warning] Multi testcase mode on" << endl; int t; cin >> t; while (t--) solve(); } return 0; }