Time Exceeded
Code
#include <bits/stdc++.h>
using namespace std;
const int M = 1e9 + 7;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
vector<int> v(n);
int totalSum = 0;
for (int &a : v)
{
cin >> a;
totalSum += a;
}
if (totalSum < k)
{
cout << "0\n";
continue;
}
vector<int> dp(totalSum + 1, 0);
dp[0] = 1;
for (int i = 0; i < n; ++i)
{
for (int j = totalSum; j >= v[i]; --j)
{
dp[j] = (dp[j] + dp[j - v[i]]);
if (dp[j] > M)
dp[j] -= M;
}
}
int result = 0;
for (int i = k; i <= totalSum; ++i)
{
result = (result + dp[i]);
if (result > M)
result -= 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++17 (G++ 13.2.0)
- Submit At
- 2024-09-05 16:50:42
- Judged At
- 2024-10-03 13:06:00
- Judged By
- Score
- 80
- Total Time
- ≥2054ms
- Peak Memory
- ≥2.059 MiB