제출 #6036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
6036		kriii	없는 등수 찾기 (GA7_rank)	C++98	100 / 100	300 ms	1096 KiB

rank

#include <stdio.h>
#include <algorithm>
using namespace std;

const long long mod = 1000000007;
int N,M,R,A[255],B[255];
long long ans = 1, prv[255][2], nxt[255][2];

int main()
{
	scanf ("%d %d",&N,&M);
	for (int i=0;i<N;i++) scanf ("%d %d",&A[i],&B[i]), ans = ans * (B[i] - A[i] + 1) % mod;
	scanf ("%d",&R);

	for (int k=0;k<=M;k++){
		for (int i=0;i<R;i++) prv[i][0] = prv[i][1] = 0; prv[0][0] = 1;
		for (int i=0;i<N;i++){
			for (int j=0;j<R;j++) nxt[j][0] = nxt[j][1] = 0;
			for (int j=0;j<R;j++){
				if (A[i] < k){
					int len = min(B[i],k-1) - A[i]  + 1;
					nxt[j][0] += prv[j][0] * len;
					nxt[j][1] += prv[j][1] * len;
				}
				if (A[i] <= k && k <= B[i]){
					nxt[j][1] += prv[j][0] + prv[j][1];
				}
				if (k < B[i]){
					int len = B[i] - max(k+1,A[i]) + 1;
					nxt[j+1][0] += prv[j][0] * len;
					nxt[j+1][1] += prv[j][1] * len;
				}
			}
			for (int j=0;j<R;j++){
				prv[j][0] = nxt[j][0] % mod;
				prv[j][1] = nxt[j][1] % mod;
			}
		}
		ans = (ans + mod - prv[R-1][1]) % mod;
	}

	printf ("%lld\n",ans);

	return 0;
}

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