I solved this problem(with right logic)but i do not know how this implementation is working. I am trying to make a prefix sum in dp array but when you print it there is no prefix array in it.(IG it's because of mod function, but i do not know it's inner working).↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define fr(i, n) for (int64_t i = 0; i < n; i++)↵
#define frn(i, a, n) for (int64_t i = a; i < n; i++)↵
#define testoutput FILE *file = fopen("test.out", "r"); if (file){fclose(file);freopen("test.out", "w", stdout); }↵
#define vet vector<int64_t>↵
#define vett vector<vector<int64_t> >↵
#define vst vector<string>↵
#define en cout << "\n";↵
#define all(v) v.begin(), v.end()↵
#define int int64_t↵
#define mp make_pair↵
#define F first↵
#define S second↵
const int mx = INT64_MAX;↵
↵
// clang++ -std=c++20 check.cpp -o a↵
// clang++ -std=c++20 random.cpp -o r↵
↵
↵
const int MOD = (1e9 + 7);↵
inline int posmod(int k)↵
{↵
return ((k % MOD) + MOD) % MOD;↵
}↵
↵
void solve()↵
{↵
int n,k;cin >> n >> k;↵
vet a(n+1);frn(i,1,n+1)cin >> a[i];↵
vett dp(n+1,vet(k+1,0));dp[0][0]=1;↵
frn(i,1,n+1){↵
fr(j,k+1){↵
int start = j-a[i];↵
if(start<=0)start=0;↵
else start = dp[i-1][start-1];↵
dp[i][j]=posmod(dp[i][j]+dp[i-1][j]-start);↵
if(j>0)dp[i][j] = posmod(dp[i][j]+dp[i][j-1]);↵
}↵
}↵
cout << dp[n][k];↵
}↵
↵
↵
int32_t main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
testoutput↵
int64_t t = 1,caseno = 1;↵
// cin >> t; ↵
while (t--)↵
{↵
// cout << "Case # " << caseno << ": "<<endl;↵
solve();↵
// cout << "\n";↵
// caseno++;↵
}↵
// cerr << "Time elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";↵
return 0;↵
}↵
~~~~~↵
↵
↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define fr(i, n) for (int64_t i = 0; i < n; i++)↵
#define frn(i, a, n) for (int64_t i = a; i < n; i++)↵
#define testoutput FILE *file = fopen("test.out", "r"); if (file){fclose(file);freopen("test.out", "w", stdout); }↵
#define vet vector<int64_t>↵
#define vett vector<vector<int64_t> >↵
#define vst vector<string>↵
#define en cout << "\n";↵
#define all(v) v.begin(), v.end()↵
#define int int64_t↵
#define mp make_pair↵
#define F first↵
#define S second↵
const int mx = INT64_MAX;↵
↵
// clang++ -std=c++20 check.cpp -o a↵
// clang++ -std=c++20 random.cpp -o r↵
↵
↵
const int MOD = (1e9 + 7);↵
inline int posmod(int k)↵
{↵
return ((k % MOD) + MOD) % MOD;↵
}↵
↵
void solve()↵
{↵
int n,k;cin >> n >> k;↵
vet a(n+1);frn(i,1,n+1)cin >> a[i];↵
vett dp(n+1,vet(k+1,0));dp[0][0]=1;↵
frn(i,1,n+1){↵
fr(j,k+1){↵
int start = j-a[i];↵
if(start<=0)start=0;↵
else start = dp[i-1][start-1];↵
dp[i][j]=posmod(dp[i][j]+dp[i-1][j]-start);↵
if(j>0)dp[i][j] = posmod(dp[i][j]+dp[i][j-1]);↵
}↵
}↵
cout << dp[n][k];↵
}↵
↵
↵
int32_t main()↵
{↵
ios_base::sync_with_stdio(0);↵
cin.tie(NULL);↵
cout.tie(NULL);↵
testoutput↵
int64_t t = 1,caseno = 1;↵
// cin >> t; ↵
while (t--)↵
{↵
// cout << "Case # " << caseno << ": "<<endl;↵
solve();↵
// cout << "\n";↵
// caseno++;↵
}↵
// cerr << "Time elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";↵
return 0;↵
}↵
~~~~~↵
↵
