제출 #754822

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
754822		denniskim	Boat (APIO16_boat)	C++17	100 / 100	1823 ms	16408 KiB

boat

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef __int128 lll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
#define MAX 9223372036854775807LL
#define MIN -9223372036854775807LL
#define INF 0x3f3f3f3f3f3f3f3f
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout << fixed; cout.precision(10);
#define sp << " "
#define en << "\n"
#define compress(v) sort(v.begin(), v.end()), v.erase(unique(v.begin(), v.end()), v.end())

ll n;
pll a[1010];
ll ss = 1000000007;
ll inv[1010];
vector<ll> zip;
ll dp[1010][1010];
ll sum[1010][1010];
ll LC[1010];
ll xjc[1010];

ll sqrmtp(ll X, ll Y)
{
	ll ret = 1;
	
	while(Y)
	{
		if(Y & 1)
			ret = ret * X % ss;
		
		X = X * X % ss;
		Y >>= 1;
	}
	
	return ret;
}

int main(void)
{
	fastio
	
	cin >> n;
	
	for(ll i = 1 ; i <= n ; i++)
	{
		cin >> a[i].fi >> a[i].se;
		
		zip.push_back(a[i].fi);
		zip.push_back(a[i].se + 1);
	}
	
	for(ll i = 1 ; i <= n ; i++)
		inv[i] = sqrmtp(i, ss - 2);
	
	compress(zip);
	
	dp[0][0] = 1;
	sum[0][0] = 1;
	
	for(ll i = 1 ; i <= n ; i++)
		sum[0][i] = 1;
	
	ll siz = (ll)zip.size();
	
	for(ll i = 1 ; i < siz ; i++)
	{
		vector<ll> num;
		
		for(ll j = 1 ; j <= n ; j++)
		{
			if(a[j].fi <= zip[i - 1] && zip[i] - 1 <= a[j].se)
				num.push_back(j);
		}
		
		ll L = zip[i] - zip[i - 1];
		LC[0] = 1;
		
		for(ll j = 1 ; j <= n ; j++)
		{
			if(L <= 0)
				break;
			
			LC[j] = LC[j - 1] * L % ss * inv[j] % ss;
			L--;
		}
		
		L = zip[i] - zip[i - 1];
		
		ll siz2 = (ll)num.size();
		
		for(ll j = 0 ; j <= siz2 ; j++)
		{
			ll gap = j;
			ll gap2 = 1;
			
			xjc[j] = 0;
			
			if(L <= 1)
				continue;
			
			xjc[j] = LC[2];
			
			for(ll k = 1 ; ; k++)
			{
				if(k + 2 > L || k > j)
					break;
				
				gap2 = gap2 * gap % ss * inv[k] % ss;
				gap--;
				xjc[j] = (xjc[j] + gap2 * LC[k + 2] % ss) % ss;
			}
		}
		
		for(ll j = 0 ; j < siz2 ; j++)
		{
			dp[i][num[j]] = (dp[i][num[j]] + sum[i - 1][num[j] - 1] * LC[1] % ss) % ss;
			
			if(L >= 2)
			{
				for(ll k = 0 ; k < j ; k++)
					dp[i][num[j]] = (dp[i][num[j]] + sum[i - 1][num[k] - 1] * xjc[j - k - 1] % ss) % ss;
			}
		}
		
		for(ll j = 0 ; j <= n ; j++)
			dp[i][j] = (dp[i][j] + dp[i - 1][j]) % ss;
		
		sum[i][0] = dp[i][0];
		
		for(ll j = 1 ; j <= n ; j++)
			sum[i][j] = (sum[i][j - 1] + dp[i][j]) % ss;
	}
	
	sum[siz - 1][n]--;
	sum[siz - 1][n] = (sum[siz - 1][n] % ss + ss) % ss;
	
	cout << sum[siz - 1][n];
	return 0;
}

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