Submission #6050

#	Time	Username	Problem	Language	Result	Execution time	Memory
6050		ainta	없는 등수 찾기 (GA7_rank)	C++98	10 / 100	0 ms	2072 KiB

rank

#include<stdio.h>
#include<algorithm>
using namespace std;
int n, m, R;
int w[251][2];
long long R1, R2, Mod = 1000000007, D[2][251][251];
void Do(int x){
	int i, j, k;
	for (i = 0; i <= n; i++){
		for (j = 0; j < R; j++){
			D[0][i][j] = D[1][i][j] = 0;
		}
	}
	D[0][0][0] = 1;
	for (i = 1; i <= n; i++){
		for (j = 0; j < R; j++){
			if (w[i][0] <= x && x <= w[i][1] && j != R-1){
				D[1][i][j + 1] = (D[1][i][j + 1] + D[0][i - 1][j] + D[1][i - 1][j]) % Mod;
			}
			for (k = 0; k < 2; k++){
				if (w[i][0] < x && j != R - 1){
					D[k][i][j + 1] = (D[k][i][j + 1] + D[k][i - 1][j] * (min(x - 1, w[i][1]) - w[i][0] + 1)) % Mod;
				}
				if (w[i][1] > x){
					D[k][i][j] = (D[k][i][j] + D[k][i - 1][j] * (w[i][1] - max(w[i][0], x + 1) + 1)) % Mod;
				}
			}
		}
	}
	R2 = (R2 + D[1][n][R - 1]) % Mod;
}
int main()
{
	int i;
	scanf("%d%d", &n, &m);
	R1 = 1;
	for (i = 1; i <= n; i++){
		scanf("%d%d", &w[i][0], &w[i][1]);
		R1 = R1*(w[i][1] - w[i][0] + 1) % Mod;
	}
	scanf("%d", &R);
	if (R == 1){
		printf("0\n");
		return 0;
	}
	for (i = 0; i <= m; i++){
		Do(i);
	}
	printf("%lld\n", (R1 - R2 + Mod) % Mod);
}

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