ll ans[n][k+1]={0};
ll sum[n][k+2]={0};
for(int i=0;i<=seq[0];i++){
ans[0][i]=1;
}
for(int i=1;i<=k+1;i++){
sum[0][i]=sum[0][i-1]+ans[0][i-1];
}
for(int i=1;i<n;i++){
for(int j=0;j<=k;j++){
ans[i][j]=sum[i-1][j+1]-sum[i-1][max(0ll,j-seq[0])];
}
for(int j=1;j<=k+1;j++){
sum[i][j]=sum[i][j-1]+ans[i][j-1];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<k+1;j++){
cout<<ans[i][j]<<" ";
}
cout<<'\n';
}
return ans[n-1][k];
Entirety of code
#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
using namespace std::chrono;
long long int p=1e9 +7;
int n,k;
ll seq[105];
bool debugging=0;
bool outputcheck=0;
bool timecheck=0;
void init(){
if(debugging){
}
else{
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>seq[i];
}
}
}
long long int modpower(ll b,ll po, ll mod=p){
long long int ans=1;
while(po){
if(po&1){
ans*=b;
ans%=mod;
}
b*=b;
b%=mod;
po>>=1;
}
return ans;
}
ll solve(){
ll ans[n][k+1]={0};
ll sum[n][k+2]={0};
/* Manual initialisation
for(int i=0;i<n;i++){
for(int j=0;j<k+1;j++){
ans[i][j]=0;
sum[i][j]=0;
}
sum[i][k+1]=0;
}
*/
for(int i=0;i<=seq[0];i++){
ans[0][i]=1;
}
for(int i=1;i<=k+1;i++){
sum[0][i]=sum[0][i-1]+ans[0][i-1];
}
for(int i=1;i<n;i++){
for(int j=0;j<=k;j++){
ans[i][j]=sum[i-1][j+1]-sum[i-1][max(0ll,j-seq[i])];
}
for(int j=1;j<=k+1;j++){
sum[i][j]=sum[i][j-1]+ans[i][j-1];
}
}
for(int i=0;i<n;i++){
for(int j=0;j<k+1;j++){
cout<<ans[i][j]<<" ";
}
cout<<'\n';
}
return ans[n-1][k];
}
ll solvebad(){
}
int output(){
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
//cin >>t;
t=1;
srand(time(0));
while(t--){
init();
if(debugging){
if(outputcheck){
if(solve()!=solvebad()){//checking for random input
output();
}
}
if(timecheck){
auto start=high_resolution_clock::now();
solve();
auto stop=high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
cout<<duration.count()<<" Fast\n";
start=high_resolution_clock::now();
solvebad();
stop=high_resolution_clock::now();
duration = duration_cast<microseconds>(stop - start);
cout<<duration.count()<<" Slow\n";
}
}
else{
cout<<solve()<<"\n";//solving it correctly
}
}
}
TC
3 4
1 2 3
This gives me a random value for ans[0][2]. Can anyone tell me why does this happen. It is given that seq[i]<=k for all i.
Question.
Find no. of ways such that \sum a_i =k Where a_i<=seq[i]