| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 6845 |
2014-07-08T06:14:17 Z |
qja0950 |
없는 등수 찾기 (GA7_rank) |
C++ |
|
472 ms |
1100 KB |
#include <stdio.h>
#define MAXN 292
#define MOD 1000000007
int N, M, R;
int A[MAXN], B[MAXN];
long long All=1;
void INPUT() {
scanf("%d %d", &N, &M);
for(int i=1; i<=N; i++) {
scanf("%d %d", &A[i], &B[i]);
All*=(long long)(B[i]-A[i]+1);
All%=MOD;
}
scanf("%d", &R);
}
int MIN(int a, int b) {
if(a<b) return a;
else return b;
}
long long Dy[2][MAXN][2];
void PROCESS() {
long long Ans=All;
for(int p=0; p<=M; p++) {
for(int t0=0; t0<2; t0++)
for(int t1=0; t1<=N; t1++)
for(int t2=0; t2<2; t2++)
Dy[t0][t1][t2]=0;
Dy[0][0][0]=1;
for(int i=1; i<=N; i++) {
int over, same, under;
if(A[i]<=p && p<=B[i]) over=B[i]-p;
else if(p<A[i]) over=B[i]-A[i]+1;
else over=0;
if(A[i]<=p && p<=B[i]) under=p-A[i];
else if(B[i]<p) under=B[i]-A[i]+1;
else under=0;
if(A[i]<=p && p<=B[i]) same=1;
else same=0;
for(int j=0; j<=N; j++) {
for(int k=0; k<=1; k++) {
Dy[i%2][j][k]=Dy[1-i%2][j][k]*(long long) under;
Dy[i%2][j][k]%=MOD;
}
}
for(int j=0; j<=N; j++) {
for(int k=0; k<=1; k++) {
Dy[i%2][j+1][k]+=Dy[1-i%2][j][k]*(long long)over;
Dy[i%2][j+1][k]%=MOD;
int maxk=MIN(k+1, 1);
Dy[i%2][j][maxk]+=Dy[1-i%2][j][k]*(long long)same;
Dy[i%2][j][maxk]%=MOD;
}
}
}
Ans+=(MOD-Dy[N%2][R-1][1]);
Ans%=MOD;
}
printf("%lld\n", Ans);
}
int main() {
// freopen("input", "r", stdin);
INPUT();
PROCESS();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
28 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
76 ms |
1100 KB |
Output is correct |
| 7 |
Correct |
112 ms |
1100 KB |
Output is correct |
| 8 |
Correct |
136 ms |
1100 KB |
Output is correct |
| 9 |
Correct |
40 ms |
1100 KB |
Output is correct |
| 10 |
Correct |
84 ms |
1100 KB |
Output is correct |
| 11 |
Correct |
356 ms |
1100 KB |
Output is correct |
| 12 |
Correct |
220 ms |
1100 KB |
Output is correct |
| 13 |
Correct |
224 ms |
1100 KB |
Output is correct |
| 14 |
Correct |
284 ms |
1100 KB |
Output is correct |
| 15 |
Correct |
236 ms |
1100 KB |
Output is correct |
| 16 |
Correct |
472 ms |
1100 KB |
Output is correct |
| 17 |
Correct |
472 ms |
1100 KB |
Output is correct |
| 18 |
Correct |
472 ms |
1100 KB |
Output is correct |
| 19 |
Correct |
472 ms |
1100 KB |
Output is correct |
| 20 |
Correct |
472 ms |
1100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
4 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
28 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
76 ms |
1100 KB |
Output is correct |
| 7 |
Correct |
112 ms |
1100 KB |
Output is correct |
| 8 |
Correct |
136 ms |
1100 KB |
Output is correct |
| 9 |
Correct |
40 ms |
1100 KB |
Output is correct |
| 10 |
Correct |
84 ms |
1100 KB |
Output is correct |
| 11 |
Correct |
356 ms |
1100 KB |
Output is correct |
| 12 |
Correct |
212 ms |
1100 KB |
Output is correct |
| 13 |
Correct |
220 ms |
1100 KB |
Output is correct |
| 14 |
Correct |
284 ms |
1100 KB |
Output is correct |
| 15 |
Correct |
236 ms |
1100 KB |
Output is correct |
| 16 |
Correct |
472 ms |
1100 KB |
Output is correct |
| 17 |
Correct |
472 ms |
1100 KB |
Output is correct |
| 18 |
Correct |
472 ms |
1100 KB |
Output is correct |
| 19 |
Correct |
472 ms |
1100 KB |
Output is correct |
| 20 |
Correct |
472 ms |
1100 KB |
Output is correct |
