oj.uz

Submission #6033

# Submission time Handle Problem Language Result Execution time Memory
6033 2014-06-15T19:11:29 Z kriii 없는 등수 찾기 (GA7_rank) C++
10 / 100
 0 ms 1096 KB 
#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+1][0] += prv[j][0] * len;
					nxt[j+1][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][0] += prv[j][0] * len;
					nxt[j][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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1096 KB Output is correct
2 Correct 0 ms 1096 KB Output is correct
3 Correct 0 ms 1096 KB Output is correct
4 Correct 0 ms 1096 KB Output is correct
5 Correct 0 ms 1096 KB Output is correct
6 Correct 0 ms 1096 KB Output is correct
7 Correct 0 ms 1096 KB Output is correct
8 Correct 0 ms 1096 KB Output is correct
9 Correct 0 ms 1096 KB Output is correct
10 Correct 0 ms 1096 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1096 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1096 KB Output isn't correct
2 Halted 0 ms 0 KB -