/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 1.066 MiB
#2 Accepted 3ms 1.07 MiB
#3 Wrong Answer 4ms 1.066 MiB
#4 Accepted 4ms 1.164 MiB
#5 Accepted 5ms 1.219 MiB
#6 Wrong Answer 6ms 1.066 MiB

Code

#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define dbg(a,b,c,d) cerr<<a<<"  "<<b<<"  "<<c<<"  "<<d<<endl;
#define kill(a) {cout<<a<<endl;continue;}
#define KILL(a) {cout<<a<<endl;return 0;}
#define debug cerr<<"Error Found"<<endl;
#define mem(a,b) memset(a,b,sizeof(a))
#define lcm(a, b) (a/__gcd(a,b))*b
#define w(t) cin>>t;while(t--)
#define pi  2 * acos(0.0)
#define endl "\n"
int t, cs = 0;
const int mxn = 2e5 + 3, mod = 1e9 + 7;
int fact[mxn];
int power(int base, int po)
{
    int res = 1;
    while(po)
    {
        if(po & 1)res = 1LL * res * base % mod;
        base = 1LL * base * base % mod, po /= 2;
    }
    return res;
}
void pre()
{
    fact[0] = 1;
    for(int i = 1; i < mxn; i++)fact[i] = 1LL * fact[i - 1] * i % mod;
}
int ncr(int n, int r)
{
    int res = fact[n];
    res = 1LL * res * power(fact[n - r], mod - 2) % mod;
    res = 1LL * res * power(fact[r], mod - 2) % mod;
    return res;
}
int32_t main()
{
    pre();
    //fast
    w(t)
    {
        int n, x;
        cin >> n >> x;
        int ar[n];
        int sum = 0;
        for(int i = 0; i < n; i++)cin >> ar[i], sum += ar[i];
        int ans = 0;
        if(x > sum)kill(ans);
        ans = power(2, n - sum) - 1;
        int tmp = ans;
        sort(ar, ar + n, greater<int>());
        int bad = 0;
        for(int i = 0; i < n; i++)
        {
            bad += ar[i];
            if(sum - bad >= x)
            {
                int a = ncr(sum, i + 1);
                ans += 1LL * tmp * a % mod, ans %= mod;
                ans += a, ans %= mod;
            }
        }
        cout << ans << endl;

    }
}

Information

Submit By
Type
Submission
Problem
P1094 Number of ways (Hard version)
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-07 17:50:17
Judged At
2024-11-11 02:23:10
Judged By
Score
7
Total Time
6ms
Peak Memory
1.219 MiB