Submission #554359

#	Time	Username	Problem	Language	Result	Execution time	Memory
554359		AmShZ	Boat (APIO16_boat)	C++11	100 / 100	1101 ms	16456 KiB

boat

# include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
# define F first
# define S second
# define endl '\n'
# define sep ' '
# define pb push_back
# define fast_io ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
 
const ll md = 1e9 + 7;//998244353;
const int xn = 1e3 + 10;
const int xm = 1e5 + 10;
const int SQ = 320;
const int sq = 1e3 + 10;
const ll inf = 1e18 + 10;
 
 
ll power(ll a, ll b) {return (!b ? 1 : (b & 1 ? a * power(a * a % md, b / 2) % md : power(a * a % md, b / 2) % md));}
ll zarb(ll a, ll b){return (a * b + 10 * md) % md;}
ll jaam(ll a, ll b){return (a + b + 10 * md) % md;}
 
 
int n, C[xn][xn], invi[xn], CR[xn][xn];
int F[xn][xn], ted, dp[xn][xn];
pii A[xn];
set <int> st;
vector <int> vec;
vector <pii> seg;

void Solve(int ind, int t){
	C[ind][0] = F[ind][0] = 1;
	for (int i = 1; i <= min(n, t); ++ i)
		C[ind][i] = 1ll * C[ind][i - 1] * (t - i + 1) % md * invi[i] % md;
	for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= min(i, t); ++ j)
				F[ind][i] = (F[ind][i] + 1ll * CR[i - 1][j - 1] * C[ind][j] % md) % md;
}

 
int main(){
	fast_io;
	
	for (int i = 0; i < xn; ++ i)
		CR[i][0] = 1;
	for (int i = 1; i < xn; ++ i)
		for (int j = 1; j <= i; ++ j)
			CR[i][j] = (CR[i - 1][j] + CR[i - 1][j - 1]) % md;
	cin >> n;
	for (int i = 1; i <= n; i ++)
		cin >> A[i].F >> A[i].S, ++ A[i].S;
	for (int i = 1; i <= n; i ++)
		st.insert(A[i].F), st.insert(A[i].S);
	for (int x : st)
		vec.push_back(x);
	for (int i = 1; i < vec.size(); i ++)
		seg.emplace_back(vec[i - 1], vec[i]);
	for (int i = 1; i < xn; i ++)
		invi[i] = power(i, md - 2);
	for (int i = 0; i < seg.size(); i ++)
		Solve(i, seg[i].S - seg[i].F);
	for (int i = 0; i < xn; ++ i)
		dp[i][0] = dp[0][i] = 1;
	for (int i = 1; i <= n; i ++){
		for (int j = 1; j <= seg.size(); j ++){
			dp[i][j] = dp[i][j - 1], ted = 0;
			for (int k = i; k >= 1; -- k)
				if (A[k].F <= seg[j - 1].F && seg[j - 1].S <= A[k].S)
					dp[i][j] = (dp[i][j] + 1ll * dp[k - 1][j - 1] * F[j - 1][++ ted] % md) % md;
		}
	}
	cout << (dp[n][seg.size()] + md - 1) % md << endl;
	
	return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 1; i < vec.size(); i ++)
      |                  ~~^~~~~~~~~~~~
boat.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  for (int i = 0; i < seg.size(); i ++)
      |                  ~~^~~~~~~~~~~~
boat.cpp:70:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |   for (int j = 1; j <= seg.size(); j ++){
      |                   ~~^~~~~~~~~~~~~

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