#340006 (C++14) No.81 すべて足すだけの簡単なお仕事です。

• 問題: No.81 すべて足すだけの簡単なお仕事です。
• ユーザー: fumiphys
• 提出日時: 2019-04-19 16:54:21
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 2 ms / 5,000 ms
• コード長: 7,083 bytes
• コンパイル時間: 2,823 ms
• コンパイル使用メモリ: 194,632 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-07-22 16:46:40
• 合計ジャッジ時間: 3,736 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
other	AC * 30

ソースコード

// includes
#include <bits/stdc++.h>

// macros
#define ll long long int
#define pb emplace_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define FI first
#define SE second
using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
const int mod = 1e9 + 7;

// solve
template <class T>bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;}
template <class T>bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;}
template <typename T> istream &operator>>(istream &is, vector<T> &vec){for(auto &v: vec)is >> v; return is;}

const ll B = 10000;
const int BW = 4;
struct BigInt{
  vector<ll> digit;
  BigInt(ll a = 0){
    digit.emplace_back(a);
    normalize();
  }
  BigInt(const string &s){
    from_string(s);
  }
  void from_string(const string &s){
    digit.clear();
    int i;
    for(i = (int)s.size() - BW; i >= 0; i-=BW){
      digit.emplace_back(stol(s.substr(i, BW)));
    }
    i += BW;
    if(i > 0)digit.emplace_back(stol(s.substr(0, i)));
  }
  void normalize(){
    ll c = 0;
    for(int i = 0; i < digit.size(); i++){
      while(digit[i] < 0){
        if(i + 1 == digit.size())digit.emplace_back(0);
        digit[i+1]--;
        digit[i] += B;
      }
      ll a = digit[i] + c;
      digit[i] = a % B;
      c = a / B;
    }
    while(c){
      digit.emplace_back(c % B);
      c /= B;
    }
    for(int i = (int)digit.size() - 1; i >= 1; i--){
      if(digit[i] == 0){
        digit.pop_back();
      }else{
        break;
      }
    }
  }
  size_t size(){
    return digit.size();
  }
  BigInt& operator=(ll a){
    digit.resize(1, a);
    normalize();
    return *this;
  }
  BigInt& operator=(const string &s){
    from_string(s);
    return *this;
  }
} ZERO(0), ONE(1);

ostream &operator<<(ostream &os, const BigInt &b){
  os << b.digit[b.digit.size() - 1];
  for(int i = (int)b.digit.size() - 2; i >= 0; i--){
    os << setw(BW) << setfill('0') << b.digit[i];
  }
  return os;
}

istream & operator>>(istream &is, BigInt &b){
  string s;
  is >> s;
  b.from_string(s);
  return is;
}

bool operator<(BigInt x, BigInt y){
  if(x.digit.size() != y.digit.size())return x.digit.size() < y.digit.size();
  for(int i = x.digit.size() - 1; i >= 0; i--){
    if(x.digit[i] != y.digit[i])return x.digit[i] < y.digit[i];
  }
  return false;
}

bool operator>(BigInt x, BigInt y){
  return y < x;
}

bool operator<=(BigInt x, BigInt y){
  return !(y < x);
}

bool operator>=(BigInt x, BigInt y){
  return !(x < y);
}

bool operator!=(BigInt x, BigInt y){
  return x < y || y < x;
}

bool operator==(BigInt x, BigInt y){
  return !(x < y) && !(y < x);
}

BigInt operator+(BigInt x, ll a){
  x.digit[0] += a;
  x.normalize();
  return x;
}

BigInt operator+(BigInt x, BigInt y){
  while(x.digit.size() < y.digit.size())x.digit.emplace_back(0);
  for(int i = 0; i < y.digit.size(); i++)x.digit[i] += y.digit[i];
  x.normalize();
  return x;
}

BigInt operator-(BigInt x, BigInt y){
  assert(x.digit.size() >= y.digit.size());
  for(int i = 0; i < y.digit.size(); i++)x.digit[i] -= y.digit[i];
  x.normalize();
  return x;
}

BigInt operator*(BigInt x, BigInt y){
  BigInt z;
  z.digit.assign(x.digit.size() + y.digit.size(), 0);
  for(int i = 0; i < x.digit.size(); i++){
    for(int j = 0; j < y.digit.size(); j++){
      z.digit[i+j] += x.digit[i] * y.digit[j];
    }
  }
  z.normalize();
  return z;
}

BigInt operator*(BigInt x, ll a){
  for(int i = 0; i < x.digit.size(); i++)x.digit[i] *= a;
  x.normalize();
  return x;
}

pair<BigInt, ll> divmod(BigInt x, ll a){
  ll c = 0;
  for(int i = (int)x.digit.size() - 1; i >= 0; i--){
    ll t = B * c + x.digit[i];
    x.digit[i] = t / a;
    c = t % a;
  }
  x.normalize();
  return make_pair(x, c);
}

BigInt operator/(BigInt x, ll a){
  return divmod(x, a).first;
}

BigInt operator%(BigInt x, ll a){
  return divmod(x, a).second;
}

pair<BigInt, BigInt> divmod(BigInt x, BigInt y){
  if(x.digit.size() < y.digit.size())return make_pair(ZERO, x);
  int F = B / (y.digit[y.digit.size() - 1] + 1);
  x = x * F; y = y * F;
  BigInt z;
  z.digit.assign(x.digit.size() - y.digit.size() + 1, 0);
  for(int k = (int)z.digit.size() - 1, i = (int)x.digit.size() - 1; k >= 0; k--, i--){
    z.digit[k] = (i + 1 < x.digit.size() ? x.digit[i+1]: 0) * B + x.digit[i];
    z.digit[k] /= y.digit[y.digit.size() - 1];
    BigInt t;
    t.digit.assign(k + y.digit.size(), 0);
    for(int m = 0; m < y.digit.size(); m++){
      t.digit[k+m] = z.digit[k] * y.digit[m];
    }
    t.normalize();
    while(x < t){
      z.digit[k] -= 1;
      for(int m = 0; m < y.digit.size(); m++){
        t.digit[k+m] -= y.digit[m];
      }
      t.normalize();
    }
    x = x - t;
  }
  z.normalize();
  return make_pair(z, x / F);
}

BigInt operator/(BigInt x, BigInt y){
  return divmod(x, y).first;
}

BigInt operator%(BigInt x, BigInt y){
  return divmod(x, y).second;
}

BigInt& operator+=(BigInt &x, ll a){
  x = x + a;
  return x;
}

BigInt &operator+=(BigInt &x, BigInt y){
  x = x + y;
  return x;
}

BigInt &operator-=(BigInt &x, BigInt y){
  x = x - y;
  return x;
}

BigInt& operator*=(BigInt &x, BigInt y){
  x = x * y;
  return x;
}

BigInt& operator/=(BigInt &x, BigInt y){
  x = x / y;
  return x;
}

BigInt& operator%=(BigInt &x, BigInt y){
  x = x % y;
  return x;
}

BigInt& operator/=(BigInt &x, ll a){
  x = x / a;
  return x;
}

BigInt& operator%=(BigInt &x, ll a){
  x = x % a;
  return x;
}

BigInt sqrt(BigInt x){
  BigInt l = 1;
  BigInt r = x;
  while(r - l > BigInt(1)){
    BigInt m = (r + l) / 2;
    if(m * m > x)r = m;
    else l = m;
  }
  return l;
}

int main(int argc, char const* argv[])
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  BigInt res(0);
  bool m = false;
  rep(i, n){
    string s;
    cin >> s;
    int at = sz(s) - 1;
    string t;
    for(int j = 0; j < sz(s); j++){
      if(s[j] == '.')at = j;
      else{
        t += s[j];
      }
    }
    for(int j = 0; j < 10 - (sz(s) - at - 1); j++)t += '0';
    bool neg = false;
    if(t[0] == '-'){
      neg = true;
      t = t.substr(1, sz(t) - 1);
    }
    BigInt tmp = BigInt(t);
    if(m == neg){
      res = res + tmp;
    }else{
      if(res > tmp){
        res = res - tmp;
      }else{
        res = tmp - res;
        m = !m;
      }
    }
  }
  if(m)cout << "-";
  cout.fill('0');
  cout << res / BigInt((ll)1e10) << ".";
  res = res % BigInt((ll)1e10);
  string t = "";
  for(int i = 0; i < min(3, sz(res.digit)); i++){
    string tt = to_string(res.digit[i]);
    reverse(all(tt));
    tt.resize(4, '0');
    reverse(all(tt));
    t = tt + t;
  }
  reverse(all(t));
  t.resize(10, '0');
  reverse(all(t));
  cout << t << endl;
	return 0;
}