Submission #262837

#	Time	Username	Problem	Language	Result	Execution time	Memory
262837		hohohaha	Boat (APIO16_boat)	C++14	9 / 100	1648 ms	40068 KiB

boat

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define ii pair<int, int>
#define vii vector<ii>

#define iii pair<int, ii>
#define viii vector<iii>

#define ld long double
#define li long long

#define eb emplace_back
#define vi vector<int>
#define fi first
#define se second

const int mod = 1e9+7, maxn = 505;

int n, l[maxn], r[maxn], low[maxn][maxn], up[maxn][maxn], C[maxn][6*maxn], back[6*maxn][maxn], fac[maxn], dp[maxn][6*maxn][2], sdp[maxn][6*maxn];
vi all;
vii seg; 

void add(int& a, int b)
{
	a = (a+b)%mod;
}
int mul(int a, int b)
{
	return a*b%mod;
}
int binpow(int x, int k)
{
	if(!k) return 1;
	int t = binpow(x, k/2);
	if(k&1) return mul(mul(t, t), x);
	return mul(t, t);
}
int inv(int x)
{
	return binpow(x, mod-2);
}
void init()
{
	for(int i=0; i<=n; i++)
	{
		if(!i) fac[i] = 1;
		else fac[i] = mul(fac[i-1], i);
	}
}
signed main()
{
	cin>>n;
	init();
	for(int i=1; i<=n; i++)
	{
		cin>>l[i]>>r[i];
		all.eb(l[i]-1);
		all.eb(r[i]+1);
		all.eb(l[i]);
		all.eb(r[i]);
	}
	all.eb(0);
	for(int i=1; i<=n; i++)
	{
		low[i][i] = l[i]; 
		up[i][i] = r[i];
		for(int j=i+1; j<=n; j++)
		{
			low[i][j] = max(low[i][j-1], l[j]);
			up[i][j] = min(up[i][j-1], r[j]);
		}
	}
	sort(begin(all), end(all));
	seg.eb(0, 0);
	for(int i=1; i<all.size(); i++)
	{
//		cout<<all[i-1]+1<<" "<<all[i]<<endl;
		if(all[i]-all[i-1]) seg.eb(all[i-1]+1, all[i]);
	}
	for(int i=1; i<seg.size(); i++)
	{
//		cout<<i<<" "<<endl;
		int range = seg[i].se - seg[i].fi+1;
		for(int j=0; j<=min(range, n); j++)
		{
//			cout<<j<<endl;
			if(!j) back[i][j]=1;
 			else back[i][j] = mul(back[i][j-1], range - j+1);
 			C[j][i] = mul(back[i][j], inv(fac[j]));
		}
	}
	dp[0][0][0] = 1;
	for(int i=0; i<=n; i++)
	{
		for(int k=0; k<seg.size(); k++)
		{
			if(i)
			{
				if(!k)
				{
					dp[i][k][0] = 1;
					dp[i][k][1] = 0;
				}
				else
				{
					for(int j=1; j<=i; j++)
					{
						add(dp[i][k][0], dp[j-1][k][1]);
						if(low[j][i]<=seg[k].fi and seg[k].se<=up[j][i])
						{
//							cout<<sdp[j-1][k-1]<<" "<<C[i-j+1][k]<<" "<<back[k][j-i+1]<<endl;
							add(dp[i][k][1], mul(sdp[j-1][k-1], C[i-j+1][k]));
//							cout<<j<<" "<<i<<" "<<k<<"fick \n";
//							cout<<low[j][i]<<" "<<up[j][i]<<e0ndl;
						}
					}
				}
//				cout<<i<<" "<<k<<": 0: "<<dp[i][k][0]<<" 1: "<<dp[i][k][1]<<endl;
			}
			add(sdp[i][k], dp[i][k][0]);
			add(sdp[i][k], dp[i][k][1]);
			if(k) add(sdp[i][k], sdp[i][k-1]);
		}
	}
	int ans = sdp[n][seg.size()-1]-1;
	while(ans<0) add(ans, mod);
	cout<<ans;	
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:79:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i=1; i<all.size(); i++)
      |               ~^~~~~~~~~~~
boat.cpp:84:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i=1; i<seg.size(); i++)
      |               ~^~~~~~~~~~~
boat.cpp:99:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for(int k=0; k<seg.size(); k++)
      |                ~^~~~~~~~~~~

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