提出 #13669371
ソースコード 拡げる
#include<bits/stdc++.h>
#include <unistd.h>
#define pb push_back
#define ll long long
int mo = 1e9+7;
// int dp[1000][1000];
using namespace std;
int main(int argc, char const *argv[])
{
// ios::sync_withss_stdio(false);
// cin.tie(0);
// cout.tie(0);
int n, k;
scanf("%d%d", &n, &k);
int a[n];
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
}
long long dp[n+1][k+1];
long long sumarr[n+1][k+1];
memset(dp, 0 , sizeof(dp));
for (int i = 0; i <= k; ++i)
{
dp[0][i] = 0;
}
dp[0][0] = 1;
for (int i = 1; i <= n; ++i)
{
for (int j = 0; j <= k; ++j)
{
if (j == 0)
{
sumarr[i-1][j] = dp[i-1][j]%mo;
}
else{
sumarr[i-1][j] = ((sumarr[i-1][j-1]) + (dp[i-1][j]))%mo;
}
}
for (int j = 0; j <= k; ++j)
{
// int sum = 0;
// for (int k = 0; k <= min(j , a[i-1]); ++k)
// {
// sum += dp[i-1][j-k];
// }
int t = min(j, a[i-1]);
if(t == j){
dp[i][j] = sumarr[i-1][j];
}
else{
dp[i][j] = sumarr[i-1][j] - sumarr[i-1][j-t-1];
}
}
}
// for (int i = 0; i <= n; ++i)
// {
// for (int j = 0; j <= k; ++j)
// {
// printf("%lld ", dp[i][j]);
// }
// printf("\n");
// }
printf("%lld\n", dp[n][k]);
// for (int i = 0; i <= n; ++i)
// {
// for (int j = 0; j <= k; ++j)
// {
// printf("%lld ", sumarr[i][j]);
// }
// printf("\n");
// }
}
提出情報
| 提出日時 |
|
| 問題 |
M - Candies |
| ユーザ |
hackerbaba |
| 言語 |
C++14 (GCC 5.4.1) |
| 得点 |
0 |
| コード長 |
1439 Byte |
| 結果 |
WA |
| 実行時間 |
217 ms |
| メモリ |
158080 KiB |
コンパイルエラー
./Main.cpp: In function ‘int main(int, const char**)’:
./Main.cpp:18:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &k);
^
./Main.cpp:22:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a[i]);
^
ジャッジ結果
| セット名 |
All |
| 得点 / 配点 |
0 / 100 |
| 結果 |
|
| セット名 |
テストケース |
| 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 |
| ケース名 |
結果 |
実行時間 |
メモリ |
| 0_00 |
AC |
1 ms |
256 KiB |
| 0_01 |
AC |
1 ms |
256 KiB |
| 0_02 |
AC |
1 ms |
256 KiB |
| 0_03 |
AC |
10 ms |
8064 KiB |
| 1_00 |
AC |
1 ms |
256 KiB |
| 1_01 |
AC |
4 ms |
3328 KiB |
| 1_02 |
AC |
1 ms |
256 KiB |
| 1_03 |
AC |
217 ms |
158080 KiB |
| 1_04 |
AC |
213 ms |
155648 KiB |
| 1_05 |
WA |
213 ms |
155520 KiB |
| 1_06 |
WA |
216 ms |
157184 KiB |
| 1_07 |
AC |
214 ms |
156160 KiB |
| 1_08 |
AC |
213 ms |
155136 KiB |
| 1_09 |
WA |
216 ms |
157696 KiB |
| 1_10 |
WA |
211 ms |
154496 KiB |
| 1_11 |
AC |
214 ms |
156032 KiB |