#746449 (C++14) No.269 見栄っ張りの募金活動

提出ソース

結果

問題	No.269 見栄っ張りの募金活動
ユーザー	gamma_kpr
提出日時	2022-03-17 17:56:51
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	19 ms / 5,000 ms
コード長	13,523 bytes
コンパイル時間	2,334 ms
コンパイル使用メモリ	193,236 KB
実行使用メモリ	19,840 KB
最終ジャッジ日時	2024-04-09 03:01:37
合計ジャッジ時間	3,155 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,948 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	8 ms 9,472 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	19 ms 19,840 KB
testcase_08	AC	2 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,948 KB
testcase_11	AC	3 ms 6,944 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	4 ms 6,948 KB
testcase_14	AC	3 ms 6,944 KB
testcase_15	AC	4 ms 6,948 KB
testcase_16	AC	2 ms 6,948 KB
testcase_17	AC	2 ms 6,948 KB
testcase_18	AC	7 ms 9,088 KB
testcase_19	AC	4 ms 6,948 KB
testcase_20	AC	2 ms 6,948 KB
testcase_21	AC	3 ms 6,944 KB
testcase_22	AC	3 ms 6,944 KB
testcase_23	AC	2 ms 6,948 KB
testcase_24	AC	3 ms 6,948 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function 'long long int fibonatti(long long int)':
main.cpp:76:12: warning: 'temp' may be used uninitialized [-Wmaybe-uninitialized]
   76 |     return count;
      |            ^~~~~
main.cpp:61:15: note: 'temp' was declared here
   61 |     long long temp;
      |               ^~~~

ソースコード

raw source code

//#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
//#include <atcoder/all>
#define ll long long
#define ull unsigned long long
//roop
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define repi(i,a,b) for(int i=a;i<b;i++)
#define repa(i,n) for(auto i : n)
#define repad(i,n) for(auto &i:n)

#define all(a) a.begin(),a.end()
#define INFint 2147483640
#define mint modint1000000007
#define mint9 modint998244353
using namespace std;
//using namespace atcoder;
 
std::ostream &operator<<(std::ostream &dest, __int128_t value) {
  std::ostream::sentry s(dest);
  if (s) {
    __uint128_t tmp = value < 0 ? -value : value;
    char buffer[128];
    char *d = std::end(buffer);
    do {
      --d;
      *d = "0123456789"[tmp % 10];
      tmp /= 10;
    } while (tmp != 0);
    if (value < 0) {
      --d;
      *d = '-';
    }
    int len = std::end(buffer) - d;
    if (dest.rdbuf()->sputn(d, len) != len) {
      dest.setstate(std::ios_base::badbit);
    }
  }
  return dest;
}
/*2進数配列+1*/
/*vector<int> twoadd(vector<int> v, int N){
    v[N-1]+=1;
    int ind = N-1;
    int j=N-1;
    for(j=N-1;j>=1;j--){
        if(v[j]>1){
            v[j-1]+=1;
            v[j]=0;
        }
    }
    return v;
}
 
/*フィボナッチ*/
long long fibonatti(long long d){
    long long count = 0;
    long long f1 = 1;
    long long f2 = 1;/*ここを変える*/
    long long temp;
    if(d == 1){
        count = f1;
    }else if(d == 2){
        count = f2;
    }else if(d==0){
        count = 1;
    }else{
        for(int i=0;i<d-2;i++){
            temp = f1+f2;
            f1 = f2;
            f2 = temp;
        }
        count = temp;
    }
    return count;
}
 
/*最大公約数*/
unsigned long long GCD(long long L,long long R){
    if(L>R){
        long long temp=R;
        R = L;
        L = temp;
    }
    unsigned long long pp=0,ppt=0;
    unsigned long long ans=0;
    if(R%L==0){
        ans = L;
    }else{
        while(true){
            ppt = pp;
            pp=R%L;
            if(pp == 0){
                ans = ppt;
                break;
            }
            R = L;
            L = pp;
        }
    }    
    return ans;    
}
 
/*最小公倍数*/
unsigned long long LCM(long long L,long long R){
    unsigned long long ans;
    unsigned long long gcd = GCD(L,R);
    ans = (L/gcd)*R;
    return ans;
}
 
/*Combination set*/
#define mod 1000000007
//#define mod 998244353
#define maxcomb 20000/*大きいものを求めるときはここを変える*/
vector<long long> fc(maxcomb+1);
vector<long long> ifc(maxcomb+1);

long long CombinationNoMOD(long long n,long long k){
    ll ans = 1;
    for(ll i = 1;i<=k;i++){
        ans *= (n-i+1);
        ans /= i;
    }
    return ans;

}

long long modpow(long long x,long long n){
    long long ans = 1;
    while(n > 0){
        if(n & 1) {
            ans = ans*x%mod;
        }
        x = x*x%mod;
        n >>= 1;
    }
    return ans;
}
void Comb(){
    fc[0]= 1;
    ifc[0]=1;
    for(long long i=0;i<maxcomb;i++){
        fc[i+1] = fc[i]*(i+1)%mod;//n!(mod)
        ifc[i+1] = ifc[i]*modpow(i+1,mod-2)%mod;//k!^{M-2} (mod)
    }
}
/*Required Comb()*/
unsigned long long Combination(long long L,long long R){
    unsigned long long up=1,ans;
    //Conb();
    if(L==0&&R==0){
        return 1;
    }else if(L<R||L<0){
        return 0;
    }else{
        long long t = ifc[L-R]*ifc[R]%mod;
        ans = t*fc[L]%mod;
    }
    return ans;
}
/*Combination set ここまで*/
 
/*素数判定*/
bool isPrime(int x){
    int i;
    if(x < 2){
        return 0;
    }else if(x == 2){
        return 1;
    }
    if(x%2 == 0) {
        return 0;
    }
    for(i = 3; i*i <= x; i += 2){
        if(x%i == 0){
            return 0;
        }
    }
    return 1;
}
 
/*桁和*/
int digsum(int n) {
    int res = 0;
    while(n > 0) {
        res += n%10;
        n /= 10;
    }
    return res;
}
 
/*約数の数*/
long long countdivisor(long long K){
    long long N = sqrt(K);
    bool b = false;
    if(sqrt(K)-N==0){
        b= true;
    }
    long long count =0;
    for(int i=0;i<N;i++){
        if(K%(i+1)==0){
            count++;
        }
    }
    if(b==false){
        count *= 2;
    }else{
        count = (count-1)*2+1;
    }
    return count;
}
 
/*約数列挙*/
vector<long long> Alldivisor(long long n){
    vector<long long> ret;
    for(int i=1;i*i<=n;i++){
        if(n%i == 0){
            ret.push_back(i);
            if(i != 1 && i*i != n){
                ret.push_back(n/i);
            }
        }
    }
    return ret;
}
/**/
template <typename T>
vector<pair<T, T>> prime_factor(T n) {
    vector<pair<T, T>> ret;
    for (T i = 2; i * i <= n; i++) {
        T tmp = 0;
        while (n % i == 0) {
            tmp++;
            n /= i;
        }
        if(tmp!=0) ret.push_back(make_pair(i, tmp));
    }
    if (n != 1) ret.push_back(make_pair(n, 1));
    return ret;
}
 
/*特定の文字カウント*/
int stringcount(string s,char c){
    return count(s.cbegin(),s.cend(),c);
}
 
/*Graph*/
using Graph = vector<vector<int>>; //グラフ型
struct Edge{
    int to; //辺の行き先
    int weight; //辺の重み
    Edge(int t,int w):to(t),weight(w){}
};
using WGraph = vector<vector<Edge>>;
/*vector<int> first_order; //行きがけ順
vector<int> last_order; //帰りがけ順 */
/*重みなし有向*/
Graph WeightlessGraph(int N,int M){
    Graph G(N);
    //vector<bool> m(N,false);
    for(int i=0;i<M;i++){
        int a,b;
        cin >> a >> b;
        G[a-1].push_back(b-1);
    }
    return G;
}
/*重みなし無向*/
Graph WeightlessNoDirectionGraph(int N,int M){
    Graph G(N);
    for(int i=0;i<M;i++){
        int a,b;
        cin >> a >> b;
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }
    return G;
}
/*重みつき*/
WGraph WeightGraph(int N,int M){
    WGraph G(N+1);
    for(int i=0;i<M;i++){
        int from, to ,weight;
        cin >> from >> to >> weight;
        G[from].push_back(Edge(to,weight));
    }
    return G;
}
/*深さ優先探索*/
vector<bool> seen;
//vector<ll> ans;
void dfs(const Graph &G, int s,int p){
    seen[s]=true;
    /*if(p!=-1){
        ans[s]+=ans[p];
    }*/
    for(auto next_v:G[s]){
        if(seen[next_v]){
            continue;
        }
        dfs(G,next_v,s);
    }
}
/*1以外の素因数の個数*/
long long prime_counter(long n) {
    long long count=0;
    bool ch = false;
    for (long i = 2; i * i <= n; i++) {
        long long tmp = 0;
        while (n % i == 0) {
            tmp++;
            n /= i;
            ch = true;
        }
        if(ch == true) count++;
        ch = false;
    }
    if (n != 1) count++;
    return count;
}
 
long long divisor(long long n){
    int i=sqrt(n);
    while(true){
        if(n%i == 0){
            return i;
        }
        i--;
    }
}
long long modpow1(long long x,long long n,long long md){
    long long ans = 1;
    while(n > 0){
        if(n & 1) {
            ans = ans*x%md;
        }
        x = x*x%md;
        n >>= 1;
    }
    return ans;
}
/*bit全探索用*/
vector<int> bitlevel;
void levelup(int N){
    bitlevel[N-1]+=1;
    int ind = N-1;
    int j=N-1;
    for(j=N-1;j>=1;j--){
        //cout << j << endl;
        if(bitlevel[j]>1){
            bitlevel[j-1]+=1;
            bitlevel[j]=0;
        }
    }
}
int vector_finder(std::vector<int> vec, int number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}


vector<ll> a;   
int binary_search(int l,int r,ll k){
    int mid = (l+r)/2;
    if(l>=r) return mid;
    if(a[mid]<k) return binary_search(mid+1,r,k);
    else return binary_search(l,mid,k);
}
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
    vector<ll> siz;
    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
        siz.assign(N,1);
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        //cout << par[y] << endl;
        //cout << siz[ry] << " " << siz[rx] << endl;
        siz[ry] += siz[rx];
        //cout << siz[ry] << endl;
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
    ll size(ll x){
        return siz[root(x)];
    }
};
template <typename T>
struct RMQ {
    const T INF = numeric_limits<T>::max();
    int n;         // 葉の数
    vector<T> dat; // 完全二分木の配列
    RMQ(int n_) : n(), dat(n_ * 4, INF) { // 葉の数は 2^x の形
        int x = 1;
        while (n_ > x) {
            x *= 2;
        }
        n = x;
    }
    void update(int i, T x) {
        i += n - 1;
        dat[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;  // parent
            dat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }
    // the minimum element of [a,b)
    T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
    T query_sub(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) {
            return INF;
        } else if (a <= l && r <= b) {
            return dat[k];
        } else {
            T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
    }
};
 
template <typename T>
struct RMQl {
    const T INF = numeric_limits<T>::max();
    int n;
    vector<T> dat, lazy;
    RMQl(int n_) : n(), dat(n_ * 4, -INF), lazy(n_ * 4, -INF) {
        int x = 1;
        while (n_ > x) x *= 2;
        n = x;
    }
    /* lazy eval */
    void eval(int k) {
        if (lazy[k] == -INF) return;  // 更新するものが無ければ終了
        if (k < n - 1) {             // 葉でなければ子に伝搬
            lazy[k * 2 + 1] = lazy[k];
            lazy[k * 2 + 2] = lazy[k];
        }
        // 自身を更新
        dat[k] = lazy[k];
        lazy[k] = -INF;
    }
    void update(int a, int b, T x, int k, int l, int r) {
        eval(k);
        if (a <= l && r <= b) {  // 完全に内側の時
            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] = max(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    void update(int a, int b, T x) { update(a, b, x, 0, 0, n); }
    T query_sub(int a, int b, int k, int l, int r) {
        eval(k);
        if (r <= a || b <= l) {  // 完全に外側の時
            return -INF;
        } else if (a <= l && r <= b) {  // 完全に内側の時
            return dat[k];
        } else {  // 一部区間が被る時
            T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
            return max(vl, vr);
        }
    }
    T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
    /* debug */
    inline T operator[](int a) { return query(a, a + 1); }
    void print() {
        for (int i = 0; i < 2 * n - 1; ++i) {
            cout << (*this)[i];
            if (i != n) cout << ",";
        }
        cout << endl;
    }
};
/*座圧*/
void compressor(vector<int> &a){
    set<int> s(all(a));
    map<int,int> d;
    int cnt = 0;
    repa(x,s) d[x] = cnt++;
    repad(x,a) x = d[x];
}
/*segment tree*/
ll op(ll a,ll b){return a+b;}
ll e(){return 0LL;}

/*長さ1の配列に対してif(a[0]==a[1])などとやると、atcoderのジャッジではtrueとなる,手元ではfalse*/
/*ここから*/

struct dpair{
    ll a,b;
    bool operator < (const dpair &p) const{
        if(p.a!= a) return p.a > a;
        else return p.b < b;
    }
    bool operator == (const dpair &p) const{
        if(p.a==a&&p.b==b) return true;
        else return false;
    }
};

vector<pair<int,int>> dir = {make_pair(1,0),make_pair(0,1)};

ll low_bo(ll l,ll r,ll n){
    ll mid = (l+r)/2;
    //cout << mid << endl;
    if(l+1>=r) return mid;
    if(mid*mid+mid>2*n) return low_bo(l,mid-1,n);
    else return low_bo(mid,r,n);
}

int main() {
    ll n,s,k;
    cin >> n >> s >> k;
    ll smk = (n-1)*n*k/2;
    //cout << smk << endl;
    s -= smk;
    if(s<0){
        cout << 0 << endl;
        exit(0);
    }
    vector<vector<ll>> dp(n+1,vector<ll>(s+1));
    dp[0][0] = 1;
    rep1(i,n+1){
        rep(j,s+1){
            //if(i==1) dp[i][j] = 1;
            if(j>=i){
                dp[i][j] = dp[i-1][j] + dp[i][j-i];
            }else dp[i][j] = dp[i-1][j];
            dp[i][j] %= mod;
        }
    }
    /*rep(i,n+1){
        rep(j,s+1){
            cout << dp[i][j] <<" ";
        }
        cout << "\n";
    }*/
    cout << dp[n][s] << endl;
    return 0;
}
/*REの時vectorのoverflow確認*/

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード