#492903 (C++14) No.1071 ベホマラー

• 問題: No.1071 ベホマラー
• ユーザー: tarattata1
• 提出日時: 2020-06-05 22:20:27
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 123 ms / 2,000 ms
• コード長: 8,238 bytes
• コンパイル時間: 1,702 ms
• コンパイル使用メモリ: 104,928 KB
• 実行使用メモリ: 9,740 KB
• 最終ジャッジ日時: 2024-12-17 16:02:02
• 合計ジャッジ時間: 3,926 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
sample	AC * 5
other	AC * 20

ソースコード

#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <iterator>
#include <cassert>
#include <numeric>
#include <functional>
//#include <numeric>
#pragma warning(disable:4996) 
 
typedef long long ll;
typedef unsigned long long ull;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF  9223300000000000000
#define LINF2 1223300000000000000
#define LINF3 1000000000000
#define INF 2140000000
const long long MOD = 1000000007;
//const long long MOD = 998244353;

using namespace std;

class bigint {
private:
  //static const int BASE = 1000, LEN = 3;
  static const int BASE = 100000000, LEN = 8;
  bool negative;
  std::vector<int> a;
  bigint& normalize();
public:
  bigint(int x = 0);
  bigint(const std::string& s);
  bigint& operator = (const bigint& x);
  bigint& operator = (int x);
  bigint& operator = (const std::string& s);
  const bool operator < (const bigint& x) const;
  const bool operator > (const bigint& x) const;
  const bool operator <= (const bigint& x) const;
  const bool operator >= (const bigint& x) const;
  const bool operator != (const bigint& x) const;
  const bool operator == (const bigint& x) const;
  bigint operator -() const;
  bigint& operator += (const bigint& x);
  bigint& operator -= (const bigint& x);
  bigint& operator *= (const bigint& x);
  bigint& operator /= (const bigint& x);
  bigint& operator %= (const bigint& x);
  const bigint operator + (const bigint& x) const;
  const bigint operator - (const bigint& x) const;
  const bigint operator * (const bigint& x) const;
  const bigint operator / (const bigint& x) const;
  const bigint operator % (const bigint& x) const;
  friend std::pair<bigint,bigint> divmod(const bigint& lhs, const bigint& rhs);
  friend const bigint abs(bigint x);
  static string tostr( const bigint& x);
};
bigint& bigint::normalize() {
  int i = a.size()-1;
  while (i >= 0 && a[i] == 0) --i;
  a.resize(i+1);
  if (a.size() == 0) negative = false;
  return *this;
}
bigint::bigint(int x) : negative(x<0) {
  x = abs(x);
  for (; x > 0; x /= BASE) a.push_back(x % BASE);
}
bigint::bigint(const std::string& s): negative(false) {
  int p = 0;
  if (s[p] == '-') { ++p; negative = true; }
  else if (s[p] == '+') { ++p; }
  for (int i = s.size()-1, v = BASE; i >= p; --i, v*=10) {
    int x = s[i]-'0';
    if (x < 0 || 9 < x) {
      printf("error: parse error:%s\n", s.c_str());
      exit(1);
    } 
    if (v == BASE) {
      v = 1;
      a.push_back(x);
    } else a.back() += (x)*v;
  }
  normalize();
}
bigint& bigint::operator = (const bigint& x) {
  negative = x.negative;
  a = x.a;
  return *this;
}
bigint& bigint::operator = (int x) { return *this = bigint(x); }
bigint& bigint::operator = (const std::string& s) { return *this = bigint(s); }
const bool bigint::operator < (const bigint& x) const {
  if (negative != x.negative) return negative < x.negative;
  if (a.size() != x.a.size()) return (a.size() < x.a.size())^negative;
  for(int i = a.size()-1; i >= 0; --i)
    if (a[i] != x.a[i]) return (a[i] < x.a[i])^negative;
  return false;
}
const bool bigint::operator > (const bigint& x) const { return x<(*this); }
const bool bigint::operator <= (const bigint& x) const { return !(x<(*this)); }
const bool bigint::operator >= (const bigint& x) const { return !((*this)<x); }
const bool bigint::operator != (const bigint& x) const { return (*this)<x || x<(*this); }
const bool bigint::operator == (const bigint& x) const { return !((*this)<x || x<(*this)); }
bigint bigint::operator -() const {
  bigint ret(*this);
  if (a.size()) ret.negative = !ret.negative;
  return ret;
}
bigint& bigint::operator += (const bigint& x) {
  if (negative != x.negative) return *this -= -x;
  if (a.size() < x.a.size()) a.resize(x.a.size());
  int tmp = 0;
  for (int i = 0; i < (int)a.size(); ++i) {
    a[i] += (i<(int)x.a.size()?x.a[i]:0) + tmp;
    tmp = a[i] / BASE;
    a[i] %= BASE;
  }
  if (tmp) a.push_back(1);
  return *this;
}
bigint& bigint::operator -= (const bigint& x) {
  if (negative != x.negative) return *this += -x;
  std::vector<int> b(x.a);
  if ((*this < x) ^ negative) {
    a.swap(b);
    negative = !negative;
  }
  for (int i = 0, tmp = 0; i < (int)a.size(); ++i) {
    a[i] += BASE - (i<(int)b.size()?b[i]:0) + tmp;
    tmp = a[i] / BASE - 1;
    a[i] %= BASE;
  }
  return this->normalize();
}
bigint& bigint::operator *= (const bigint& x) {
  negative ^= x.negative;
  std::vector<int> c(a.size()*x.a.size()+1);
  for (int i = 0; i < (int)a.size(); ++i) {
    long long tmp = 0;
    for (int j = 0; j < (int)x.a.size(); ++j) {
      long long v = (long long)a[i] * x.a[j] + c[i+j] + tmp;
      tmp = v / BASE;
      c[i+j] = (int)(v % BASE);
    }
    if (tmp) c[i+x.a.size()] += (int)tmp;
  }
  a.swap(c);
  return this->normalize();
}
bigint& bigint::operator /= (const bigint& x) {
  return *this = divmod(*this,x).first;
}
bigint& bigint::operator %= (const bigint& x) {
  return *this = divmod(*this,x).second;
}
const bigint bigint::operator + (const bigint& x) const {
  bigint res(*this); return res += x;
}
const bigint bigint::operator - (const bigint& x) const {
  bigint res(*this); return res -= x;
}
const bigint bigint::operator * (const bigint& x) const {
  bigint res(*this); return res *= x;
}
const bigint bigint::operator / (const bigint& x) const {
  bigint res(*this); return res /= x;
}
const bigint bigint::operator % (const bigint& x) const {
  bigint res(*this); return res %= x;
}
std::pair<bigint,bigint> divmod(const bigint& lhs, const bigint& rhs) {
  if (!rhs.a.size()) {
    printf("error: division by zero\n");
    exit(1);
  }
  bigint x(abs(rhs)), q, r;
  for (int i = lhs.a.size()-1; i >= 0; --i) {
    r = r * bigint::BASE + lhs.a[i];
    int head = 0, tail = bigint::BASE;
    if (r >= x) {
      while (head + 1 < tail) {
        int mid = (head + tail) / 2;
        if (x * bigint(mid) > r) tail = mid;
        else head = mid;
      }
      r -= x * head;
    }
    q.a.push_back(head);
  }
  reverse(q.a.begin(), q.a.end());
  bool neg = lhs.negative ^ lhs.negative;
  q.negative = neg; r.negative = neg;
  return std::make_pair(q.normalize(), r.normalize());
}
const bigint abs(bigint x) {
  x.negative = false;
  return x;
}
string bigint::tostr( const bigint& x) {
    string a;
    if (x.negative) a += "-";
    if (!x.a.size()) a += "0";
    else a += to_string((long long)x.a.back());

    for (int i=x.a.size()-2; i>=0; --i) {
        char tmp[bigint::LEN+1]={0};
        sprintf(tmp, "%0*d", bigint::LEN, x.a[i]);
        a += string(tmp);
    }
    return a;
}

bigint gcd(bigint a, bigint b) {
    if(b == 0) return a;
    return gcd(b,a%b);
}

#define PRINT(x)    printf("%s\n", bigint::tostr(x).c_str());

/*
int main() {
  char stra[105]={0};
  char strb[105]={0};
  scanf("%s", &stra);
  scanf("%s", &strb);

  bigint a(stra);
  bigint b(strb);

  PRINT(a);
  PRINT(b);
  PRINT(-a);
  PRINT(-b);
  PRINT(abs(a));
  PRINT(abs(b));
  PRINT(a<b);
  PRINT(a>b);
  PRINT(a<=b);
  PRINT(a>=b);
  PRINT(a!=b);
  PRINT(a==b);
  PRINT(a+b);
  PRINT(a-b);
  PRINT(a*b);
  PRINT(a/b);
  PRINT(a%b);
  return 0;
}
*/


void solve()
{
    int n, K, x, y;
    scanf("%d%d%d%d", &n, &K, &x, &y);

    vector<int> a(n);
    int i;
    for (i = 0; i < n; i++) {
        int tmp;
        scanf("%d", &tmp);
        int tmp2=(tmp - 1) / K;
        if ((tmp - 1) % K) tmp2++;
        a[i] = tmp2;
    }
    sort(a.rbegin(), a.rend());

    vector<bigint> s(n + 1);
    for (i = 0; i < n; i++) {
        s[i + 1] = s[i] + (bigint)a[i];
    }

    bigint ans = bigint(s[n]) * bigint(x);
    for (i = 0; i < n; i++) {
        bigint ans0 = (bigint)(s[i + 1] - (bigint)(i+1)*(bigint)a[i])*(bigint)x;
        ans0 = ans0 + (bigint)y*(bigint)a[i];
        bigint diff = ans - ans0;
        if (abs(diff) == diff) {
            ans = ans0;
        }
    }
    PRINT(ans);

    return;
}


int main(int argc, char* argv[])
{
#if 1
    solve();
#else
    int T;
    scanf("%d", &T);
    int t;
    for(t=0; t<T; t++) {
        //printf("Case #%d: ", t+1);
        solve();
    }
#endif
    return 0;
}