제출 #236368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
236368		LordOfIran	Boat (APIO16_boat)	C++14	100 / 100	514 ms	9172 KiB

boat

//                             In The Name Of Allah
//                              Mohammad Hosseini
#include <bits/stdc++.h>
#define	ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define int long long
#define ld long double
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std; 

const int N = 2000, OO = 1e9 + 7, T = 20, M = 1e9 + 7, P = 6151, SQ = 800, lg = 20;
typedef pair <int, int> pii;
pii p[N];
int dp[N][N], inv[N];
vector <int> g[N];

int pw(int x, int y) {
	if(y == 0)
		return 1;
	int cnt = pw(x, y / 2);
	cnt = (cnt * cnt) % M;
	if(y % 2)
		cnt = (cnt * x) % M;
	return cnt;
}

int32_t main() {
    use_fast;
    int n;
    cin >> n;
    vector <int> v = {0, OO};	
	for(int i = 1; i < N - 100; i++)
		inv[i] = pw(i, M - 2);
    for(int i = 1; i <= n; i++) {
    	cin >> p[i].ff >> p[i].ss;
    	p[i].ss++;
    	v.pb(p[i].ff);
    	v.pb(p[i].ss);
	}
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
	for(int i = 1; i < (int)v.size(); i++)
    	dp[0][i] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j < (int)v.size(); j++) {
			dp[i][j] = dp[i][j - 1];
			if(!(p[i].ff <= v[j - 1] && v[j] <= p[i].ss)) 
				continue;
			int l = v[j] - v[j - 1], up = (l * (l - 1) / 2) % M, nxt = 1;
			dp[i][j] = (dp[i][j] + dp[i - 1][j - 1] * l) % M;
			for(int k = (int)g[j].size() - 1; k >= 0; k--) {
				dp[i][j] = (dp[i][j] + dp[g[j][k] - 1][j - 1] * up) % M;
				up = (up * (l + nxt)) % M;
				up = (up * inv[nxt + 2]) % M;
				nxt++;
			}
			g[j].pb(i);
		}
		for(int j = 1; j < (int)v.size(); j++) 
			dp[i][j] = (dp[i][j] + dp[i - 1][j]) % M;
	}
	cout << (dp[n][(int)v.size() - 1] - 1 + M) % M << endl;
	return 0;
} 
/*
be carefull :
1- if not solve after 20 min, read again twice
2- after submit read the code again
3- fun with contest
4- ... 
*/

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42