Submission #10405906
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; } pref[0] = dp[0]; for(int i=1;i<=k;i++) { pref[i] = pref[i-1] + dp[i]; } for(int i=2;i<=n;i++) { cin>>a[i]; memset(dp, 0, sizeof(dp)); for(int j=k;j>=0;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]]; dp[j] %= mod; } pref[0] = dp[0]; 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 | 837 Byte |
Status | WA |
Exec Time | 81 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 | WA | 2 ms | 1024 KB |
0_01 | AC | 1 ms | 256 KB |
0_02 | AC | 1 ms | 1024 KB |
0_03 | AC | 4 ms | 1792 KB |
1_00 | AC | 1 ms | 256 KB |
1_01 | AC | 2 ms | 1792 KB |
1_02 | AC | 5 ms | 1024 KB |
1_03 | AC | 81 ms | 1792 KB |
1_04 | WA | 73 ms | 1792 KB |
1_05 | WA | 73 ms | 1792 KB |
1_06 | WA | 75 ms | 1792 KB |
1_07 | WA | 73 ms | 1792 KB |
1_08 | WA | 73 ms | 1792 KB |
1_09 | WA | 75 ms | 1792 KB |
1_10 | WA | 72 ms | 1792 KB |
1_11 | WA | 73 ms | 1792 KB |