Submission #3814751
Source Code Expand
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
using namespace std;
typedef pair<int, int> P;
typedef long long int ll;
const ll MOD=1e9+7;
ll dp1[2005][2005];//dp1[i][j]:左からi個だけ使ってj個選ぶ方法
ll dp2[2005][2005];//右からi個
//a:indexは1から
int a[2001];
int main(){
int N,M,Q;
cin>>N>>M>>Q;
rep(i,1,N+1) cin>>a[i];
int k[Q], x[Q];
rep(i,0,Q) cin>>k[i]>>x[i];
rep(i,0,N+1) dp1[i][0]=1;
rep(i,1,N+1){
rep(j,1,M+1){
if(j>=a[i]+1) dp1[i][j]=(dp1[i-1][j]+dp1[i][j-1]-dp1[i-1][j-a[i]-1]+MOD)%MOD;
else dp1[i][j]=(dp1[i-1][j]+dp1[i][j-1])%MOD;
}
}
rep(i,0,N+1) dp2[i][0]=1;
rep(i,1,N+1){
rep(j,1,M+1){
if(j>=a[N+1-i]+1) dp2[i][j]=(dp2[i-1][j]+dp2[i][j-1]-dp2[i-1][j-a[N+1-i]-1]+MOD)%MOD;
else dp2[i][j]=(dp2[i-1][j]+dp2[i][j-1])%MOD;
}
}
rep(i,0,Q){
ll ans=0;
rep(l,0,M-x[i]+1){
ans+=(dp1[k[i]-1][l]*dp2[N-k[i]][M-x[i]-l])%MOD;
ans%=MOD;
}
cout<< ans<<"\n";
}
}
Submission Info
Submission Time |
|
Task |
D - 注文の多い高橋商店 |
User |
yuki1997 |
Language |
C++14 (GCC 5.4.1) |
Score |
80 |
Code Size |
1214 Byte |
Status |
TLE |
Exec Time |
2104 ms |
Memory |
71424 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Subtask4 |
Score / Max Score |
0 / 0 |
10 / 10 |
20 / 20 |
50 / 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 |
AC |
2 ms |
2304 KB |
subtask1_01.txt |
AC |
2 ms |
2304 KB |
subtask1_02.txt |
AC |
2 ms |
2304 KB |
subtask1_03.txt |
AC |
2 ms |
2304 KB |
subtask1_04.txt |
AC |
2 ms |
2560 KB |
subtask1_05.txt |
AC |
2 ms |
4864 KB |
subtask1_06.txt |
AC |
2 ms |
4864 KB |
subtask1_07.txt |
AC |
3 ms |
4864 KB |
subtask1_08.txt |
AC |
2 ms |
4864 KB |
subtask2_01.txt |
AC |
31 ms |
5632 KB |
subtask2_02.txt |
AC |
88 ms |
6528 KB |
subtask2_03.txt |
AC |
58 ms |
6400 KB |
subtask3_01.txt |
AC |
37 ms |
33024 KB |
subtask3_02.txt |
AC |
71 ms |
62976 KB |
subtask3_03.txt |
AC |
63 ms |
62976 KB |
subtask4_01.txt |
TLE |
2104 ms |
55808 KB |
subtask4_02.txt |
TLE |
2104 ms |
69504 KB |
subtask4_03.txt |
AC |
295 ms |
66048 KB |
subtask4_04.txt |
TLE |
2104 ms |
6656 KB |
subtask4_05.txt |
TLE |
2104 ms |
70784 KB |
subtask4_06.txt |
TLE |
2104 ms |
67328 KB |
subtask4_07.txt |
AC |
427 ms |
71424 KB |