結果
問題 | No.1071 ベホマラー |
ユーザー |
![]() |
提出日時 | 2020-06-05 21:33:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 102 ms / 2,000 ms |
コード長 | 1,676 bytes |
コンパイル時間 | 5,590 ms |
コンパイル使用メモリ | 233,820 KB |
最終ジャッジ日時 | 2025-01-10 22:13:32 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 20 |
ソースコード
#pragma GCC optimize("Ofast")#include <bits/stdc++.h>#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>using namespace std;using namespace __gnu_pbds;using ll = long long;using u64 = uint_fast64_t;using pii = pair<int, int>;using pll = pair<long long, long long>;#define rep(i, n) for(int i = 0; i < (n); ++i)#define all(x) (x).begin(),(x).end()constexpr char ln = '\n';constexpr long long MOD = 1000000007;//constexpr long long MOD = 998244353;template<class T1, class T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true;} return false; }template<class T1, class T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true;} return false; }inline int popcount(int x) {return __builtin_popcount(x);}inline int popcount(long long x) {return __builtin_popcountll(x);}void print() { cout << "\n"; }template<class T, class... Args>void print(const T &x, const Args &... args) {cout << x << " ";print(args...);}///////////////////////////////////////////////////////////////////////////////////////////////////////////////int main() {ios::sync_with_stdio(false); cin.tie(nullptr);ll N,K,X,Y; cin >> N >> K >> X >> Y;vector<ll> A(N);rep(i,N) cin >> A[i];auto calc=[&](ll x) {ll ret = x*Y;rep(i,N) {ll val = A[i] - K*x;if (val > 1) {ret += (val-1+K-1)/K*X;}}return ret;};ll ok = 0;ll ng = 2e9;while (ng - ok > 1) {ll mid = (ok+ng)/2;if (calc(mid) - calc(mid-1) <= 0) ok = mid;else ng = mid;}cout << calc(ok) << ln;}