Submission #10405763
Source Code Expand
#include <bits/stdc++.h> #define ll long long #define pb push_back #define mp make_pair using namespace std; const int maxn = 110; const int maxk = 100100; const ll mod = 1e9 + 7; ll n, k; ll a[maxn]; ll dp[maxk]; ll pref[maxk]; int main() { cin>>n>>k; cin>>a[1]; for(int i=0;i<=a[1];i++) { dp[i] = 1LL; } for(int i=0;i<k;i++) { pref[i] += dp[i]; pref[i+1] += pref[i]; } for(int i=2;i<=n;i++) { cin>>a[i]; memset(dp, 0, sizeof(dp)); for(int j=k;j>=1;j--) { if(j - a[i] <= 0) { //cout<<j<<": "<<pref[j]<<"\n"; dp[j] += pref[j]; dp[j] %= mod; } else dp[j] += pref[j] - pref[j-a[i]-1]; dp[j] %= mod; } for(int j=1;j<=k;j++) { pref[j] = pref[j-1] + dp[j]; pref[j] %= mod; } } cout<<dp[k]<<"\n"; }
Submission Info
Submission Time | |
---|---|
Task | M - Candies |
User | someone123321 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 813 Byte |
Status | WA |
Exec Time | 100 ms |
Memory | 1792 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 100 | ||||
Status |
|
Set Name | Test Cases |
---|---|
All | 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_00 | AC | 2 ms | 1024 KB |
0_01 | AC | 1 ms | 256 KB |
0_02 | WA | 1 ms | 1024 KB |
0_03 | WA | 5 ms | 1792 KB |
1_00 | AC | 1 ms | 256 KB |
1_01 | AC | 2 ms | 1792 KB |
1_02 | WA | 5 ms | 1024 KB |
1_03 | WA | 100 ms | 1792 KB |
1_04 | AC | 92 ms | 1792 KB |
1_05 | WA | 91 ms | 1792 KB |
1_06 | AC | 94 ms | 1792 KB |
1_07 | AC | 92 ms | 1792 KB |
1_08 | AC | 92 ms | 1792 KB |
1_09 | AC | 94 ms | 1792 KB |
1_10 | WA | 91 ms | 1792 KB |
1_11 | AC | 92 ms | 1792 KB |