Submission #624918

#	Time	Username	Problem	Language	Result	Execution time	Memory
624918		QwertyPi	Boat (APIO16_boat)	C++14	36 / 100	2081 ms	8652 KiB

boat

#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 / 9
• Subtask 2: 0 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42