| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 6327 |
2014-06-28T07:35:38 Z |
jhs7jhs |
없는 등수 찾기 (GA7_rank) |
C++ |
|
268 ms |
2496 KB |
#include<stdio.h>
int n,m;
long long man[300][2]={{0}};
long long dp[300][300]={{0}},dp2[300][300]={{0}};
int main()
{
long long MD = 1000000007;
long long p,q,r,ans=0,all=1;
int i,j,k,ra;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%lld%lld",&man[i][0],&man[i][1]);
all *= (man[i][1] - man[i][0] + 1);
all %= MD;
}
scanf("%d",&ra);
if(ra == 1){
printf("0\n");
return 0;
}
for(i=1;i<=m;i++){
for(j=1;j<=n;j++){
for(k=0;k<ra;k++) dp[j][k] = dp2[j][k] = 0;
}
p = ((man[1][1]<i)?0:((man[1][0]>=i)?(man[1][1]-man[1][0]+1):(man[1][1]-i+1)));
q = ((man[1][0]>=i)?0:((man[1][1]<i)?(man[1][1]-man[1][0]+1):(i-man[1][0])));
r = ((man[1][1]<i+1)?0:((man[1][0]>=i+1)?(man[1][1]-man[1][0]+1):(man[1][1]-i)));
dp[1][0] = q%MD, dp[1][1] = p%MD;
dp2[1][0] = q%MD, dp2[1][1] = r%MD;
for(j=2;j<=n;j++){
p = ((man[j][1]<i)?0:((man[j][0]>=i)?(man[j][1]-man[j][0]+1):(man[j][1]-i+1)));
q = ((man[j][0]>=i)?0:((man[j][1]<i)?(man[j][1]-man[j][0]+1):(i-man[j][0])));
r = ((man[j][1]<i+1)?0:((man[j][0]>=i+1)?(man[j][1]-man[j][0]+1):(man[j][1]-i)));
for(k=0;k<=j && k<ra;k++){
dp[j][k] = (dp[j-1][k] * q % MD + ((k)?(dp[j-1][k-1] * p % MD):0))%MD;
dp2[j][k] = (dp2[j-1][k] * q % MD + ((k)?(dp2[j-1][k-1] * r % MD):0))%MD;
}
}
ans += (dp[n][ra-1]-((i==m)?0:dp2[n][ra-1]));
while(ans<0) ans += MD;
ans %= MD;
}
ans = all - ans;
while(ans < 0) ans += MD;
printf("%lld\n",ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 10 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 11 |
Correct |
4 ms |
2496 KB |
Output is correct |
| 12 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 13 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 14 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 15 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 16 |
Correct |
4 ms |
2496 KB |
Output is correct |
| 17 |
Correct |
4 ms |
2496 KB |
Output is correct |
| 18 |
Correct |
4 ms |
2496 KB |
Output is correct |
| 19 |
Correct |
4 ms |
2496 KB |
Output is correct |
| 20 |
Correct |
4 ms |
2496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2496 KB |
Output is correct |
| 5 |
Correct |
12 ms |
2496 KB |
Output is correct |
| 6 |
Correct |
24 ms |
2496 KB |
Output is correct |
| 7 |
Correct |
20 ms |
2496 KB |
Output is correct |
| 8 |
Correct |
68 ms |
2496 KB |
Output is correct |
| 9 |
Correct |
0 ms |
2496 KB |
Output is correct |
| 10 |
Correct |
40 ms |
2496 KB |
Output is correct |
| 11 |
Correct |
40 ms |
2496 KB |
Output is correct |
| 12 |
Correct |
8 ms |
2496 KB |
Output is correct |
| 13 |
Correct |
92 ms |
2496 KB |
Output is correct |
| 14 |
Correct |
28 ms |
2496 KB |
Output is correct |
| 15 |
Correct |
104 ms |
2496 KB |
Output is correct |
| 16 |
Correct |
164 ms |
2496 KB |
Output is correct |
| 17 |
Correct |
168 ms |
2496 KB |
Output is correct |
| 18 |
Correct |
4 ms |
2496 KB |
Output is correct |
| 19 |
Correct |
268 ms |
2496 KB |
Output is correct |
| 20 |
Correct |
260 ms |
2496 KB |
Output is correct |
