Submission #6012

#	Time	Username	Problem	Language	Result	Execution time	Memory
6012		model_code	없는 등수 찾기 (GA7_rank)	C++98	100 / 100	92 ms	2228 KiB

rank

#include<stdio.h>
#define mod 1000000007

typedef long long lld;

int n, m, r, a[270], b[270];
lld dy1[270][270], dy2[270][270], dap=1;

void countk(int k){
	int i, j;
	lld u, d1, d2;
	dy1[0][0]=dy2[0][0]=1;
	for(i=1; i<=n; i++){
		if(b[i]<k)d1=d2=b[i]-a[i]+1, u=0;
		else if(a[i]>k)u=b[i]-a[i]+1, d1=d2=0;
		else d1=k-a[i]+1, d2=k-a[i], u=b[i]-k;
		for(j=0; j<=i; j++){
			dy1[i][j] = d1*dy1[i-1][j], dy2[i][j] = d2*dy2[i-1][j];
			if(j)dy1[i][j] += u*dy1[i-1][j-1], dy2[i][j] += u*dy2[i-1][j-1];
			dy1[i][j] %= mod, dy2[i][j] %= mod;
		}
	}
	dap -= (dy1[n][r-1]-dy2[n][r-1]);
	dap %= mod;
	if(dap<0)dap += mod;
}

int main(){
	int i;
	scanf("%d%d", &n, &m);
	for(i=1; i<=n; i++)scanf("%d%d", &a[i], &b[i]), dap=dap*(b[i]-a[i]+1)%mod;
	scanf("%d", &r);
	for(i=0; i<=m; i++)countk(i);
	printf("%lld", dap);
	return 0;
}

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