結果
| 問題 | No.1686 Geschenkt |
| ユーザー |
 milkcoffee
|
| 提出日時 | 2021-09-24 21:22:13 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 6 ms / 2,000 ms |
| コード長 | 9,155 bytes |
| コンパイル時間 | 3,452 ms |
| コンパイル使用メモリ | 234,980 KB |
| 実行使用メモリ | 11,264 KB |
| 最終ジャッジ日時 | 2024-07-05 09:56:18 |
| 合計ジャッジ時間 | 3,995 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 5 ms
11,136 KB |
| testcase_01 | AC | 4 ms
11,136 KB |
| testcase_02 | AC | 5 ms
11,108 KB |
| testcase_03 | AC | 5 ms
11,024 KB |
| testcase_04 | AC | 5 ms
11,264 KB |
| testcase_05 | AC | 4 ms
11,108 KB |
| testcase_06 | AC | 4 ms
11,028 KB |
| testcase_07 | AC | 4 ms
11,120 KB |
| testcase_08 | AC | 6 ms
11,136 KB |
| testcase_09 | AC | 4 ms
11,136 KB |
ソースコード
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define ll long long
#define forin(in ,n) for(ll i=0; i<n; i++) cin>>in[i]
#define forout(out) for(ll i=0; i<(ll)out.size(); i++) cout<<out[i]<<endl
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rep_up(i, a, n) for (ll i = a; i < n; ++i)
#define rep_down(i, a, n) for (ll i = a; i >= n; --i)
#define P pair<ll, ll>
#define pb push_back
#define all(v) v.begin(), v.end()
#define fi first
#define se second
#define vvvvll vector<vector<vector<vector<ll>>>>
#define vvvll vector<vector<vector<ll>>>
#define vvll vector<vector<ll>>
#define vll vector<ll>
#define pqll priority_queue<ll>
#define pqllg priority_queue<ll, vector<ll>, greater<ll>>
template<class T> using V = vector<T>;
constexpr ll INF = (1ll << 60);
constexpr ll mod = 1000000007;
//constexpr ll mod = 998244353;
constexpr double pi = 3.14159265358979323846;
template <typename T>
inline bool chmax(T &a, T b) {
if (a < b) {
a = b;
return 1;
}
return 0;
}
template <typename T>
inline bool chmin(T &a, T b) {
if (a > b) {
a = b;
return 1;
}
return 0;
}
template <typename T>
void pt(T val) {
cout << val << "\n";
}
template <typename T>
void pt_vll(vector<T> &v) {
ll vs = v.size();
rep(i, vs) {
cout << v[i];
if (i == vs - 1)
cout << "\n";
else
cout << " ";
}
}
ll mypow(ll a, ll n) {
ll ret = 1;
if(n==0) return 1;
if(a==0) return 0;
rep(i, n) {
if (ret > (ll)(9e18 + 10) / a) return -1;
ret *= a;
}
return ret;
}
long long modpow(long long a, long long n, long long mod) {
long long res = 1;
while (n > 0) {
if (n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
long long modinv(long long a, long long m) {
long long b = m, u = 1, v = 0;
while (b) {
long long t = a / b;
a -= t * b; swap(a, b);
u -= t * v; swap(u, v);
}
u %= m;
if (u < 0) u += m;
return u;
}
struct UnionFind {
vector<ll> par,size;
UnionFind(ll N) : par(N) { //最初はすべてが根であるとして初期化
size.resize(N,1);
for(ll i=0;i<N;i++) par[i] = i;
}
ll root(ll x){ //データxの木の根を再帰で得る
if (par[x] == x) return x;
return par[x] = root(par[x]);
}
void unite(ll x, ll y){ //xとyの木を併合
ll rx = root(x);
ll ry = root(y);
if(rx == ry) return; //同じ木にあるときはそのまま
if(size[rx]>size[ry]){
par[ry]=rx;
size[rx] += size[ry];
}else{
par[rx] = ry;
size[ry] += size[rx];
}
return;
}
bool same(ll x, ll y){ //2つのデータx,yが属する木が同じならtrue
ll rx = root(x);
ll ry = root(y);
return rx == ry;
}
ll treesize(ll x){return size[root(x)];}
};
const int MAX = 2010000;
long long fac[MAX], finv[MAX], inv[MAX];
// テーブルを作る前処理
void COMinit() {
fac[0] = fac[1] = 1;
finv[0] = finv[1] = 1;
inv[1] = 1;
for (ll i = 2; i < MAX; i++){
fac[i] = fac[i - 1] * i % mod;
inv[i] = mod - inv[mod%i] * (mod / i) % mod;
finv[i] = finv[i - 1] * inv[i] % mod;
}
}
// 二項係数計算
long long COM(ll n, ll k){
if (n < k) return 0;
if (n < 0 || k < 0) return 0;
return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
/* SegTreeLazy<X,M>(n,fx,fa,fm,ex,em): モノイド(集合X, 二項演算fx,fa,fm, 単位元ex,em)についてサイズnで構築
set(int i, X x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
update(i,x): i 番目の要素を x に更新。O(log(n))
query(a,b): [a,b) 全てにfxを作用させた値を取得。O(log(n))
*/
template <typename X, typename M>
struct SegTreeLazy {
using FX = function<X(X, X)>;
using FA = function<X(X, M)>;
using FM = function<M(M, M)>;
int n;
FX fx;
FA fa;
FM fm;
const X ex;
const M em;
vector<X> dat;
vector<M> lazy;
SegTreeLazy(int n_, FX fx_, FA fa_, FM fm_, X ex_, M em_)
: n(), fx(fx_), fa(fa_), fm(fm_), ex(ex_), em(em_), dat(n_ * 4, ex), lazy(n_ * 4, em) {
int x = 1;
while (n_ > x) x *= 2;
n = x;
}
void set(int i, X x) { dat[i + n - 1] = x; }
void build() {
for (int k = n - 2; k >= 0; k--) dat[k] = fx(dat[2 * k + 1], dat[2 * k + 2]);
}
/* lazy eval */
void eval(int k) {
if (lazy[k] == em) return; // 更新するものが無ければ終了
if (k < n - 1) { // 葉でなければ子に伝搬
lazy[k * 2 + 1] = fm(lazy[k * 2 + 1], lazy[k]);
lazy[k * 2 + 2] = fm(lazy[k * 2 + 2], lazy[k]);
}
// 自身を更新
dat[k] = fa(dat[k], lazy[k]);
lazy[k] = em;
}
void update(int a, int b, M x, int k, int l, int r) {
eval(k);
if (a <= l && r <= b) { // 完全に内側の時
lazy[k] = fm(lazy[k], x);
eval(k);
} else if (a < r && l < b) { // 一部区間が被る時
update(a, b, x, k * 2 + 1, l, (l + r) / 2); // 左の子
update(a, b, x, k * 2 + 2, (l + r) / 2, r); // 右の子
dat[k] = fx(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
void update(int a, int b, M x) { update(a, b, x, 0, 0, n); }
X query_sub(int a, int b, int k, int l, int r) {
eval(k);
if (r <= a || b <= l) { // 完全に外側の時
return ex;
} else if (a <= l && r <= b) { // 完全に内側の時
return dat[k];
} else { // 一部区間が被る時
X vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
X vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
return fx(vl, vr);
}
}
X query(int a, int b) { return query_sub(a, b, 0, 0, n); }
};
/*
using X = ll;
using M = ll;
auto fx = [](X x1, X x2) -> X { return min(x1, x2); };
auto fa = [](X x, M m) -> X { return m; };
auto fm = [](M m1, M m2) -> M { return m2; };
int ex = numeric_limits<int>::max();
int em = numeric_limits<int>::max();
SegTreeLazy<X, M> rmq(n, fx, fa, fm, ex, em);
rep(i,n){
rmq.set(i,0);
}
rmq.build(); //設置
*/
/* BIT: RAQ対応BIT
初期値は a_1 = a_2 = ... = a_n = 0
・add(l,r,x): [l,r) に x を加算する
・sum(i): a_1 + a_2 + ... + a_i を計算する
計算量は全て O(logn)
*/
template <typename T>
struct BIT {
int n; // 要素数
vector<T> bit[2]; // データの格納先
BIT(int n_) { init(n_); }
void init(int n_) {
n = n_ + 1;
for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
}
void add_sub(int p, int i, T x) {
for (int idx = i; idx < n; idx += (idx & -idx)) {
bit[p][idx] += x;
}
}
void add(int l, int r, T x) { // [l,r) に加算
add_sub(0, l, -x * (l - 1));
add_sub(0, r, x * (r - 1));
add_sub(1, l, x);
add_sub(1, r, -x);
}
T sum_sub(int p, int i) {
T s(0);
for (int idx = i; idx > 0; idx -= (idx & -idx)) {
s += bit[p][idx];
}
return s;
}
T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i; }
};
vector<ll> enum_div(ll n){ //約数全列挙
vector<ll> ret;
for(ll i = 1 ; i*i <= n ; ++i){
if(n%i == 0){
ret.push_back(i);
if(i*i != n){
ret.push_back(n/i);
}
}
}
return ret;
}
void make_prime(vector<ll> &ret, ll n) { //素因数分解
ll x = n;
for (ll i = 2; i * i <= x; i++) {
while (n % i == 0) {
n /= i;
ret.push_back(i);
}
}
if (n != 1) {
ret.push_back(n);
}
return;
}
vector<bool> prime(1000010, true);
vector<ll> pri(1000010);
vector<bool> isprime(int N) { //素数判定
if (N >= 0) prime[0] = false;
if (N >= 1) prime[1] = false;
for (ll i = 2; i * i <= N; i++) {
if (!prime[i]) {
continue;
}
for (ll j = i * i; j <= N; j += i) {
if(prime[j]) pri[j]=i;
prime[j] = false;
}
}
return prime;
}
//素因数分解: void make_prime(vector<ll> &ret, ll n)
//素数判定: vector<bool> isprime(int N)
//約数全列挙: vector<ll> enum_div(ll n)
void solve(){
ll n,m,k,cnt=0,sum=0,ans=0;
cin>>n;
vll a(40);
rep(i,n){
ll x;
cin>>x;
a[x]++;
}
rep_up(i,1,40){
if(a[i-1]==0) ans+=a[i]*i;
}
cout<<ans<<endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
//cout << fixed << setprecision(16);
//ll T;
//cin>>T;
//rep(ca,T)
solve();
}