Submission #6839

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

rank

#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 && i+j>=R && j>=2) {
					Ans+=Dy[N%2][i][j];
					Ans%=MOD;
				}
			}
		}
	}
	printf("%lld\n", Ans);
}
int main() {
	INPUT();
	PROCESS();
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40