oj.uz

Submission #624918

# Submission time Handle Problem Language Result Execution time Memory
624918 2022-08-09T05:39:26 Z QwertyPi Boat (APIO16_boat) C++14
36 / 100
 2000 ms 8652 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 520;
const int M = 1e9 + 7;
int a[N], b[N];
int d[N * 2];
int dp[2][N * 2][N];

int n, m;

int pm(int a, int b){
	if(b == 0) return 1;
	return pm(a * a % M, b / 2) * (b % 2 ? a : 1) % M;
}

int mi(int a){
	return pm(a, M - 2);
}

int fact[N];

int32_t main(){
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> a[i] >> b[i];
	}
	vector<int> sp;
	sp.push_back(0);
	sp.push_back(1);
	for(int i = 0; i < n; i++){
		sp.push_back(a[i]);
		sp.push_back(b[i] + 1);
	}
	sort(sp.begin(), sp.end());
	sp.resize(unique(sp.begin(), sp.end()) - sp.begin());
	m = sp.size();
	{
		map<int, int> M;
		for(int i = 0; i < m; i++) M[sp[i]] = i;
		for(int i = 0; i < n; i++) a[i] = M[a[i]], b[i] = M[b[i] + 1];
	}
	for(int i = 0; i < m - 1; i++){
		d[i] = sp[i + 1] - sp[i];
	}
	int ans = 0;
	/*
	for(int j = 0; j < m; j++){
		for(int k = 0; k <= n; k++){
			cout << dp[0][j][k] << ' ';
		}
		cout << endl;
	}
	cout << endl;
	*/
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			for(int k = 1; k <= n; k++){
				dp[(i + 1) % 2][j][k] = dp[i % 2][j][k];
			}
		}
		int s[m + 1] = {0};
		for(int j = 0; j < m; j++){
			for(int k = 0; k <= n; k++){
				s[j + 1] += dp[i % 2][j][k];
			}
			s[j] %= M;
			s[j + 1] += s[j];
		}
		/*
		for(int j = 0; j < m; j++){
			for(int k = 0; k <= n; k++){
				cout << dp[(i + 1) % 2][j][k] << ' ';
			}
			cout << endl;
		}
		cout << endl;
		*/
		for(int j = a[i]; j < b[i]; j++){
			dp[(i + 1) % 2][j][1] += (s[j] + 1) * d[j] % M;
			for(int k = 1; k < n; k++){
				dp[(i + 1) % 2][j][k + 1] += dp[i % 2][j][k] * (d[j] - k) % M * mi(k + 1) % M;
			}
		}
		for(int j = 0; j < m; j++){
			for(int k = 1; k <= n; k++){
				dp[(i + 1) % 2][j][k] %= M;
			}
		}
		if(i == 0){
			dp[0][0][0] = 0; 
		}
		/*
		for(int j = 0; j < m; j++){
			for(int k = 0; k <= n; k++){
				cout << dp[(i + 1) % 2][j][k] << ' ';
			}
			cout << endl;
		}
		cout << endl;
		*/
	}
	
	for(int j = 0; j < m; j++){
		for(int k = 1; k <= n; k++){
			ans += dp[n % 2][j][k];
		}
	}
	ans %= M;
	cout << ans << endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 772 ms 8652 KB Output is correct
2 Correct 732 ms 8560 KB Output is correct
3 Correct 793 ms 8560 KB Output is correct
4 Correct 771 ms 8572 KB Output is correct
5 Correct 831 ms 8532 KB Output is correct
6 Correct 771 ms 8652 KB Output is correct
7 Correct 797 ms 8652 KB Output is correct
8 Correct 785 ms 8532 KB Output is correct
9 Correct 772 ms 8532 KB Output is correct
10 Correct 795 ms 8560 KB Output is correct
11 Correct 753 ms 8556 KB Output is correct
12 Correct 802 ms 8556 KB Output is correct
13 Correct 763 ms 8556 KB Output is correct
14 Correct 798 ms 8560 KB Output is correct
15 Correct 778 ms 8560 KB Output is correct
16 Correct 168 ms 1804 KB Output is correct
17 Correct 183 ms 1876 KB Output is correct
18 Correct 167 ms 1848 KB Output is correct
19 Correct 171 ms 1932 KB Output is correct
20 Correct 183 ms 1876 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 772 ms 8652 KB Output is correct
2 Correct 732 ms 8560 KB Output is correct
3 Correct 793 ms 8560 KB Output is correct
4 Correct 771 ms 8572 KB Output is correct
5 Correct 831 ms 8532 KB Output is correct
6 Correct 771 ms 8652 KB Output is correct
7 Correct 797 ms 8652 KB Output is correct
8 Correct 785 ms 8532 KB Output is correct
9 Correct 772 ms 8532 KB Output is correct
10 Correct 795 ms 8560 KB Output is correct
11 Correct 753 ms 8556 KB Output is correct
12 Correct 802 ms 8556 KB Output is correct
13 Correct 763 ms 8556 KB Output is correct
14 Correct 798 ms 8560 KB Output is correct
15 Correct 778 ms 8560 KB Output is correct
16 Correct 168 ms 1804 KB Output is correct
17 Correct 183 ms 1876 KB Output is correct
18 Correct 167 ms 1848 KB Output is correct
19 Correct 171 ms 1932 KB Output is correct
20 Correct 183 ms 1876 KB Output is correct
21 Execution timed out 2081 ms 7764 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 1876 KB Output is correct
2 Correct 121 ms 1968 KB Output is correct
3 Correct 145 ms 1976 KB Output is correct
4 Correct 146 ms 1996 KB Output is correct
5 Correct 153 ms 1876 KB Output is correct
6 Correct 211 ms 1972 KB Output is correct
7 Correct 218 ms 1972 KB Output is correct
8 Correct 209 ms 1976 KB Output is correct
9 Correct 217 ms 1972 KB Output is correct
10 Correct 213 ms 1972 KB Output is correct
11 Correct 158 ms 1876 KB Output is correct
12 Correct 130 ms 1980 KB Output is correct
13 Correct 142 ms 1876 KB Output is correct
14 Correct 144 ms 1972 KB Output is correct
15 Correct 148 ms 1972 KB Output is correct
16 Correct 100 ms 1288 KB Output is correct
17 Correct 80 ms 1356 KB Output is correct
18 Correct 86 ms 1236 KB Output is correct
19 Correct 82 ms 1236 KB Output is correct
20 Correct 100 ms 1248 KB Output is correct

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 772 ms 8652 KB Output is correct
2 Correct 732 ms 8560 KB Output is correct
3 Correct 793 ms 8560 KB Output is correct
4 Correct 771 ms 8572 KB Output is correct
5 Correct 831 ms 8532 KB Output is correct
6 Correct 771 ms 8652 KB Output is correct
7 Correct 797 ms 8652 KB Output is correct
8 Correct 785 ms 8532 KB Output is correct
9 Correct 772 ms 8532 KB Output is correct
10 Correct 795 ms 8560 KB Output is correct
11 Correct 753 ms 8556 KB Output is correct
12 Correct 802 ms 8556 KB Output is correct
13 Correct 763 ms 8556 KB Output is correct
14 Correct 798 ms 8560 KB Output is correct
15 Correct 778 ms 8560 KB Output is correct
16 Correct 168 ms 1804 KB Output is correct
17 Correct 183 ms 1876 KB Output is correct
18 Correct 167 ms 1848 KB Output is correct
19 Correct 171 ms 1932 KB Output is correct
20 Correct 183 ms 1876 KB Output is correct
21 Execution timed out 2081 ms 7764 KB Time limit exceeded
22 Halted 0 ms 0 KB -