Submission #1517106
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, pii> pip;
const ll INF = 1ll<<29;
const ll MOD = 1000000007;
const double EPS = 1e-10;
const bool debug = 0;
//----------------------//
int N, M, Q;
int a[2000];
ll dp[2001][2001], dp2[2001][2001];
int main() {
cin >> N >> M >> Q;
REP(i, N) scanf("%d", a + i);
REP(i, N + 1) dp[i][0] = 1;
REP(i, N + 1) {
FOR(j, 1, M + 1) {
if (j - a[i] - 1 >= 0) dp[i + 1][j] = dp[i + 1][j - 1] + dp[i][j] - dp[i][j - a[i] - 1] + MOD;
else dp[i + 1][j] = dp[i + 1][j - 1] + dp[i][j];
dp[i + 1][j] %= MOD;
}
}
REP(i, N) dp[i][0] = 1;
REP(i, N) {
FOR(j, 1, M + 1) {
dp2[i][j] = dp[N][j] - dp[N][j - 1] + MOD;
if (j - a[i] - 1 >= 0) dp2[i][j] += dp2[i][j - a[i] - 1];
dp2[i][j] %= MOD;
}
}
REP(i, Q) {
int k, x;
scanf("%d %d", &k, &x);
printf("%lld\n", dp2[k - 1][M - x]);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 注文の多い高橋商店 |
User |
tkmst201 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1367 Byte |
Status |
RE |
Exec Time |
159 ms |
Memory |
62208 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:26:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP(i, N) scanf("%d", a + i);
^
./Main.cpp:48:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &k, &x);
^
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Subtask4 |
Score / Max Score |
0 / 0 |
0 / 10 |
0 / 20 |
0 / 50 |
0 / 20 |
Status |
|
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
Subtask1 |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt |
Subtask2 |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt |
Subtask3 |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt |
Subtask4 |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask4_01.txt, subtask4_02.txt, subtask4_03.txt, subtask4_04.txt, subtask4_05.txt, subtask4_06.txt, subtask4_07.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
2 ms |
2304 KB |
sample_02.txt |
WA |
2 ms |
2304 KB |
subtask1_01.txt |
WA |
2 ms |
2304 KB |
subtask1_02.txt |
AC |
2 ms |
2304 KB |
subtask1_03.txt |
WA |
2 ms |
2304 KB |
subtask1_04.txt |
WA |
2 ms |
2560 KB |
subtask1_05.txt |
WA |
2 ms |
4864 KB |
subtask1_06.txt |
AC |
2 ms |
4864 KB |
subtask1_07.txt |
WA |
2 ms |
4864 KB |
subtask1_08.txt |
WA |
2 ms |
4864 KB |
subtask2_01.txt |
WA |
15 ms |
5248 KB |
subtask2_02.txt |
WA |
27 ms |
5760 KB |
subtask2_03.txt |
WA |
27 ms |
5632 KB |
subtask3_01.txt |
WA |
24 ms |
33024 KB |
subtask3_02.txt |
RE |
128 ms |
32128 KB |
subtask3_03.txt |
RE |
129 ms |
32128 KB |
subtask4_01.txt |
WA |
159 ms |
53632 KB |
subtask4_02.txt |
RE |
129 ms |
32128 KB |
subtask4_03.txt |
WA |
133 ms |
62208 KB |
subtask4_04.txt |
WA |
114 ms |
3328 KB |
subtask4_05.txt |
RE |
127 ms |
32128 KB |
subtask4_06.txt |
RE |
128 ms |
32128 KB |
subtask4_07.txt |
RE |
125 ms |
32128 KB |