oj.uz

답안 #6845

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
6845 2014-07-08T06:14:17 Z qja0950 없는 등수 찾기 (GA7_rank) C++
100 / 100
 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();
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 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

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 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

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 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

Subtask #4
40.0 / 40.0

# 결과 실행 시간 메모리 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