Submission #6842

#	Time	Username	Problem	Language	Result	Execution time	Memory
6842		qja0950	없는 등수 찾기 (GA7_rank)	C++98	0 / 100	0 ms	1104 KiB

rank

#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 MAX(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=MAX(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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40