oj.uz

Submission #624915

# Submission time Handle Problem Language Result Execution time Memory
624915 2022-08-09T05:08:37 Z QwertyPi Boat (APIO16_boat) C++14
0 / 100
 940 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];
int C(int n, int r){
	if(n < r) return 0;
	return fact[n] * mi(fact[r]) % M * mi(fact[n - r]) % M;
}

int32_t main(){
	cin >> n;
	fact[0] = 1;
	for(int i = 1; i <= n; i++){
		fact[i] = (fact[i - 1] * i) % M;
	}
	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] * C(d[j], 1) % M * mi(C(d[j], 0)) % M;
			for(int k = 1; k < n; k++){
				dp[(i + 1) % 2][j][k + 1] += dp[i % 2][j][k] * C(d[j], k + 1) % M * mi(C(d[j], k)) % 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];
			}
		}
	}
	for(int j = 0; j < m; j++){
		for(int k = 1; k <= n; k++){
			ans += dp[n % 2][j][k];
		}
	}
	ans %= M;
	/*
	for(int i = 0; i <= n; i++){
		for(int j = 0; j < m; j++){
			for(int k = 0; k <= n; k++){
				cout << dp[i][j][k] << ' ';
			}
			cout << endl;
		}
		cout << endl;
	}
	*/
	cout << ans << endl;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 940 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 940 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 Runtime error 2 ms 2132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

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