
Begin: 2020-03-08 10:30 UTC+7
Display Picture and Down Payment
End: 2020-03-12 14:30 UTC+7
32:48:34
Elapsed: 32:48:34RunningRemaining: 67:11:25
Overview
Problem
Status
Rank (32:48:28)
0 Comments
Previous12345…Next
Username
Prob
	Result
	Time
(ms)	Mem
(MB)	Lang
	Submit Time
naufalhumam
E
Wrong Answer
C++
2 hr ago
naufalhumam
E
Time Limit Exceeded
C++
2 hr ago
     
All Copyright Reserved © 2010-2020 Xu Han
Server Time: 2020-03-09 19:18:34 UTC+7

#24658393 | naufalhumam's solution for [Problem E]
Status
Wrong Answer
Length
1075
Lang
C++14 (GCC 5.3.0)
Submitted
2020-03-09 17:42:52
Shared

8.0 / 16.0
Select Code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define endl "\n"
const long long mod=1e9+7;
const double pi=acos(-1);
const long long inf=1000000000000000005LL;

int n,k,arr[100100],dp[110][100010];
bool hah[110][100010];
ll hitung(ll x,ll y){
	if(x==n)
		if(y==0)
			return 1;
		else
			return 0;
	if(hah[x][y])
		return dp[x][y];
	for(int i=0;i<=arr[x];i++)
		if(y>=i){
			dp[x][y]=dp[x][y]+hitung(x+1,y-i);
			dp[x][y]=dp[x][y]%mod;
		}
	hah[x][y]=true;
	return dp[x][y];
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
	cin>>n>>k;
	for(int i=0;i<n;i++)
		cin>>arr[i];
	for(int i=0;i<n;i++)
		dp[i][0]=1;
	for(int i=n-1;i>=0;i--){
		for(int j=1;j<=k;j++){
			if(i==n-1){
				if(j<=arr[i]){
					dp[i][j]=dp[i][j-1]+1;
				}else{
					dp[i][j]=dp[i][j-1];
				}
			}else{
				int h=j,l=max(0,j-arr[i]);
				dp[i][j]=dp[i][j-1]+((l==0)?dp[i+1][h]:dp[i+1][h]-dp[i+1][l-1]+mod)%mod;
			}
		}
	}
	cout<<(dp[0][k]-dp[0][k-1]+mod)%mod<<endl;
}