Time Exceeded
Code
#include <bits/stdc++.h>
using namespace std;
#define ll int
const int M = 1e9 + 7;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
ll n, k;
cin >> n >> k;
vector<ll> v(n);
ll totalSum = 0;
for (ll &a : v)
{
cin >> a;
totalSum += a;
}
if (totalSum < k)
{
cout << "0\n";
continue;
}
vector<ll> dp(totalSum + 1, 0);
dp[0] = 1;
for (ll i = 0; i < n; ++i)
{
for (ll j = totalSum; j >= v[i]; --j)
{
dp[j] = (dp[j] + dp[j - v[i]]) % M;
}
}
ll result = 0;
for (ll i = k; i <= totalSum; ++i)
{
result = (result + dp[i]) % M;
}
cout << (result - 1 + M) % M << '\n';
}
return 0;
}
Information
- Submit By
- Type
- Submission
- Problem
- P1094 Number of ways (Hard version)
- Contest
- Brain Booster #5
- Language
- C++20 (G++ 13.2.0)
- Submit At
- 2024-09-05 17:26:05
- Judged At
- 2024-10-03 13:04:10
- Judged By
- Score
- 80
- Total Time
- ≥2093ms
- Peak Memory
- ≥2.07 MiB