oj.uz

Submission #624917

# Submission time Handle Problem Language Result Execution time Memory
624917 2022-08-09T05:28:05 Z QwertyPi Boat (APIO16_boat) C++14
0 / 100
 959 ms 8544 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];
	}
	dp[0][0][0] = 1;
	int ans = 0;
	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 = a[i]; j < b[i]; j++){
			dp[(i + 1) % 2][j][1] += s[j] * 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;
			}
		}
		for(int j = 0; j < m; j++){
			for(int k = 1; k <= n; k++){
				ans += dp[i % 2][j][k];
			}
		}
		if(i == 0){
			dp[0][0][0] = 0; 
		}
	}
	
	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
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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