| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 6840 |
2014-07-08T05:36:47 Z |
qja0950 |
없는 등수 찾기 (GA7_rank) |
C++ |
|
1500 ms |
3088 KB |
#include <stdio.h>
#define MAXN 292
#define MOD 1000000007
int N, M, R;
int A[MAXN], B[MAXN];
void INPUT() {
scanf("%d %d", &N, &M);
for(int i=1; i<=N; i++)
scanf("%d %d", &A[i], &B[i]);
scanf("%d", &R);
}
long long Dy[2][MAXN][MAXN];
int Check[2][MAXN][MAXN];
void PROCESS() {
long long Ans=0;
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<=N; 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<=N; 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<=N; k++) {
Dy[i%2][j+1][k]+=Dy[1-i%2][j][k]*(long long)over;
Dy[i%2][j+1][k]%=MOD;
Dy[i%2][j][k+1]+=Dy[1-i%2][j][k]*(long long)same;
Dy[i%2][j][k+1]%=MOD;
}
}
}
for(int i=0; i<=N; i++) {
for(int j=0; j<=N; j++) {
if(i<R-1 && i+j>=R && j>=2) {
Ans+=Dy[N%2][i][j];
Ans%=MOD;
}
}
}
}
printf("%lld\n", Ans);
}
int main() {
// freopen("input", "r", stdin);
INPUT();
PROCESS();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 4 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 5 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 6 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 7 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 8 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 9 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 10 |
Correct |
0 ms |
3088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 2 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 3 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 4 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 5 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 6 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 7 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 8 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 9 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 10 |
Correct |
0 ms |
3088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
3088 KB |
Output is correct |
| 2 |
Correct |
68 ms |
3088 KB |
Output is correct |
| 3 |
Correct |
52 ms |
3088 KB |
Output is correct |
| 4 |
Correct |
216 ms |
3088 KB |
Output is correct |
| 5 |
Correct |
1132 ms |
3088 KB |
Output is correct |
| 6 |
Execution timed out |
1500 ms |
3084 KB |
Program timed out |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
3088 KB |
Output is correct |
| 2 |
Correct |
68 ms |
3088 KB |
Output is correct |
| 3 |
Correct |
48 ms |
3088 KB |
Output is correct |
| 4 |
Correct |
216 ms |
3088 KB |
Output is correct |
| 5 |
Correct |
1128 ms |
3088 KB |
Output is correct |
| 6 |
Execution timed out |
1500 ms |
3084 KB |
Program timed out |
| 7 |
Halted |
0 ms |
0 KB |
- |
