oj.uz

Submission #425319

# Submission time Handle Problem Language Result Execution time Memory
425319 2021-06-12T21:20:14 Z ksun48 Boat (APIO16_boat) C++14
27 / 100
 2000 ms 31416 KB 
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long LL;
LL n;
LL a[1100];
LL b[1100];
LL included[1100][1100];
LL length[1100];
LL dp[2][1100][1100];
LL lenchoose[1100][1100];
LL invlist[1100];
LL powmod(LL z1, LL e){
	if(e == 0) return 1;
	LL c = powmod(z1,e/2);
	c = (c*c) % MOD;
	if(e % 2 == 0) return c;
	return (c*z1)%MOD;
}
LL inv(LL z1){
	return powmod(z1,MOD-2) % MOD;
}

int main(){
	set<LL> st;
	cin >> n;
	st.insert(0);
	st.insert(1);
	int t1 = 0;
	for(int i = 1; i <= n; i++){
		cin >> a[i] >> b[i];
		st.insert(a[i]);
		st.insert(b[i]+1);
		t1 += b[i]-a[i];
	}
	st.insert(1000000005);
	st.insert(1000000006);
	int cur = 0;
	for(int i = 1; i < 1100; i++){
		invlist[i] = inv(i);
	}
	/*if(t1 <= 1100000){
		return 0;
	}*/
	while(st.size() >= 2){
		set<LL>::iterator c = st.begin();
		int l = *c;
		c++;
		int r = *c;
		st.erase(st.begin());
		included[0][cur] = 0;
		included[n+1][cur] = 0;
		length[cur] = r-l;
		for(int i = 1; i <= n; i++){
			if(a[i] <= l && r-1 <= b[i]){
				included[i][cur] = 1;
			} else {
				included[i][cur] = 0;
			}
		}
		cur++;
	}
	included[0][0] = 1;	
	included[n+1][cur-1] = 1;
	dp[0][0][1] = 1;
	for(int i = 0; i < cur; i++){
		int l = length[i];
		for(int j = 0; j < 510; j++){
			if(j > l){
				lenchoose[i][j] = 0;
			} else if(j == 0){
				lenchoose[i][j] = 1;
			} else {
				lenchoose[i][j] = lenchoose[i][j-1];
				lenchoose[i][j] *= (LL)(l-j+1);
				lenchoose[i][j] %= MOD;
				lenchoose[i][j] *= invlist[j];
				lenchoose[i][j] %= MOD;
			}
		}
	}
	for(int s = 0; s <= n; s++){
		for(int j = 0; j < 1100; j++){
			for(int k = 0; k < 510; k++){
				dp[1-s%2][j][k] = 0;
			}
		}
		for(int l = 1; l < cur; l++){
			dp[1-s%2][l][1] += dp[1-s%2][l-1][1];
			dp[1-s%2][l][1] %= MOD;
			for(int k = 1; k <= cur && k <= 510; k++){
				dp[1-s%2][l][1] += lenchoose[l-1][k]*dp[s%2][l-1][k];
				dp[1-s%2][l][1] %= MOD;
			}
		}
		for(int l = 0; l < cur; l++){
			if(!included[s+1][l]){
				dp[1-s%2][l][1] = 0;
			}
		}
		for(int j = 0; j < cur; j++){
			for(int k = 1; k <= cur; k++){
				dp[1-s%2][j][k] += dp[s%2][j][k];
				dp[1-s%2][j][k] %= MOD;
				if(included[s+1][j]){
					dp[1-s%2][j][k+1] += dp[s%2][j][k];
					dp[1-s%2][j][k+1] %= MOD;
				}
			}
		}
	}
	cout << (dp[1-n%2][cur-1][1]+MOD-1) % MOD << endl;
	return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 31416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 31416 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 20068 KB Output is correct
2 Correct 122 ms 20072 KB Output is correct
3 Correct 147 ms 20072 KB Output is correct
4 Correct 120 ms 20080 KB Output is correct
5 Correct 171 ms 20044 KB Output is correct
6 Correct 114 ms 20044 KB Output is correct
7 Correct 142 ms 20072 KB Output is correct
8 Correct 162 ms 20072 KB Output is correct
9 Correct 147 ms 20068 KB Output is correct
10 Correct 126 ms 19968 KB Output is correct
11 Correct 128 ms 20128 KB Output is correct
12 Correct 121 ms 20064 KB Output is correct
13 Correct 118 ms 20068 KB Output is correct
14 Correct 135 ms 20072 KB Output is correct
15 Correct 139 ms 20072 KB Output is correct
16 Correct 136 ms 19244 KB Output is correct
17 Correct 92 ms 19300 KB Output is correct
18 Correct 115 ms 19320 KB Output is correct
19 Correct 129 ms 19276 KB Output is correct
20 Correct 102 ms 19276 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2067 ms 31416 KB Time limit exceeded
2 Halted 0 ms 0 KB -