oj.uz

Submission #6844

# Submission time Handle Problem Language Result Execution time Memory
6844 2014-07-08T06:10:13 Z qja0950 없는 등수 찾기 (GA7_rank) C++
30 / 100
 380 ms 1104 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][3];
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<=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<=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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1104 KB Output is correct
2 Correct 0 ms 1104 KB Output is correct
3 Correct 0 ms 1104 KB Output is correct
4 Correct 0 ms 1104 KB Output is correct
5 Correct 0 ms 1104 KB Output is correct
6 Correct 0 ms 1104 KB Output is correct
7 Correct 0 ms 1104 KB Output is correct
8 Correct 0 ms 1104 KB Output is correct
9 Correct 0 ms 1104 KB Output is correct
10 Correct 0 ms 1104 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1104 KB Output is correct
2 Correct 0 ms 1104 KB Output is correct
3 Correct 0 ms 1104 KB Output is correct
4 Correct 0 ms 1104 KB Output is correct
5 Correct 0 ms 1104 KB Output is correct
6 Correct 0 ms 1104 KB Output is correct
7 Correct 0 ms 1104 KB Output is correct
8 Correct 0 ms 1104 KB Output is correct
9 Correct 0 ms 1104 KB Output is correct
10 Correct 0 ms 1104 KB Output is correct

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1104 KB Output is correct
2 Correct 4 ms 1104 KB Output is correct
3 Correct 0 ms 1104 KB Output is correct
4 Correct 8 ms 1104 KB Output is correct
5 Correct 28 ms 1104 KB Output is correct
6 Correct 80 ms 1104 KB Output is correct
7 Correct 120 ms 1104 KB Output is correct
8 Correct 148 ms 1104 KB Output is correct
9 Correct 44 ms 1104 KB Output is correct
10 Correct 88 ms 1104 KB Output is correct
11 Incorrect 380 ms 1104 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1104 KB Output is correct
2 Correct 4 ms 1104 KB Output is correct
3 Correct 0 ms 1104 KB Output is correct
4 Correct 8 ms 1104 KB Output is correct
5 Correct 32 ms 1104 KB Output is correct
6 Correct 84 ms 1104 KB Output is correct
7 Correct 120 ms 1104 KB Output is correct
8 Correct 148 ms 1104 KB Output is correct
9 Correct 44 ms 1104 KB Output is correct
10 Correct 88 ms 1104 KB Output is correct
11 Incorrect 380 ms 1104 KB Output isn't correct
12 Halted 0 ms 0 KB -