제출 #6785

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

rank

#include <cstdio>
#include <algorithm>

using namespace std;
typedef long long ll;
const int MAX = 420, MOD = 1000000007;

int n, m, a[MAX], b[MAX], target;

void input(){
	scanf("%d%d", &n, &m);

	int i;
	for(i = 1; i<=n; i++)
		scanf("%d%d", &a[i], &b[i]);

	scanf("%d", &target);
}

void add(int &t, ll val){
	val += t;
	t = val%MOD;
}

int dp[MAX][2][2];

void solve(){
	int res = 1, i, j, k;
	for(i = 1; i<=n; i++)
		res = (ll)res*(b[i]-a[i]+1)%MOD;

	for(i = 0; i<=m; i++){
		for(k = 0; k<=target-1; k++){
			dp[k][0][0] = 0;
			dp[k][0][1] = 0;
			dp[k][1][0] = 0;
			dp[k][1][1] = 0;
		}
		dp[0][0][0] = 1;

		for(j = 1; j<=n; j++){
			bool c = j&1;

			for(k = 0; k<=target-1; k++){
				ll up = max(0, min(b[j]-i, b[j]-a[j]+1));
				ll mid = a[j] <= i && i <= b[j];
				ll down = max(0, min(i-a[j], b[j]-a[j]+1));

				//m+1 ~ b[j]
				add(dp[k+1][0][c], dp[k][0][!c]*up);
				add(dp[k+1][1][c], dp[k][1][!c]*up);

				//m
				add(dp[k][1][c], dp[k][0][!c]*mid);
				add(dp[k][1][c], dp[k][1][!c]*mid);

				//a[j] ~ m-1
				add(dp[k][0][c], dp[k][0][!c]*down);
				add(dp[k][1][c], dp[k][1][!c]*down);
			}

			for(k = 0; k<=target-1; k++){
				dp[k][0][!c] = 0;
				dp[k][1][!c] = 0;
			}
		}

		add(res, MOD-dp[target-1][1][n&1]);
	}
	
	printf("%d\n", res);
}

int main(){
	input();

	solve();

	return 0;
}

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