Submission #956849

#	Time	Username	Problem	Language	Result	Execution time	Memory
956849		8pete8	Boat (APIO16_boat)	C++17	100 / 100	503 ms	33440 KiB

boat

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<numeric> //gcd(a,b)
#include<cmath>
#include<set>
#include<cassert>
#include<algorithm>
#include<bitset> 
#include<stack>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define pppiiii pair<pii,pii>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back
//#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#define int int64_t
const int mxn=1000+10,minf=-1e18,mod=1e9+7,inf=1e18,lg=30;
int dp[mxn+10][mxn+10],ncr[mxn+10][mxn+10],sum[mxn+10][mxn+10];
int ncr2[mxn+10][mxn+10],choose[mxn+10][mxn+10];
int fac[mxn+10];
inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while (true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}
inline void out(int x) {
	int rev=x, c=0;
	if(!x) {
		putchar_unlocked('0');
		return;
	}
	while(!(rev%10)) {
		++c;
		rev/=10;
	}
	rev=0;
	while(x) {
		rev=rev*10+x%10;
		x/=10;
	}
	while(rev) {
		putchar_unlocked(rev%10+'0');
		rev/=10;
	}
	while(c--)
		putchar_unlocked('0');
}
int inv(int x){
	int ex=mod-2,ans=1;
	while(ex){
		if(ex&1)ans=(ans*x)%mod;
		x=(x*x)%mod;
		ex>>=1;
	}
	return ans;
}
int get(int i,int j){
	if(choose[i][j]!=-1)return choose[i][j];
	int sum=0;
	for(int k=2;k<=j;k++){
		int x=(ncr2[i][k]*(ncr[j-2][k-2]))%mod;
		if(x)sum=(sum+x)%mod;
		else break;
	}
	choose[i][j]=sum;
	return choose[i][j];
}
int32_t main(){
	fastio
	int n=in();
	vector<pii>v(n+1);
	vector<int>com;
	for(int i=1;i<=n;i++){
		v[i].f=in();
		v[i].s=in();
		v[i].f--;
	}
	for(int i=1;i<=n;i++)com.pb(v[i].f),com.pb(v[i].s);
	sort(all(com));
	com.erase(unique(all(com)),com.end());
	/*
	ncr i,j->(i,j+1)
	x=(x*(len-j+1))*inv(j)
	*/
	ncr[0][0]=1;
	for(int i=1;i<=n;i++)for(int j=0;j<=n;j++){
		if(j)ncr[i][j]=(ncr[i-1][j]+ncr[i-1][j-1])%mod;
		else ncr[i][j]=ncr[i-1][j];
	}
	for(int i=1;i<com.size();i++){
		int len=com[i]-com[i-1];
		ncr2[i][1]=len;	
		for(int j=2;j<=min(n,len);j++)ncr2[i][j]=((ncr2[i][j-1]*(len-j+1))%mod*inv(j))%mod;
	}
	for(int i=1;i<com.size();i++)for(int j=2;j<=n;j++)choose[i][j]=-1;
	for(int i=1;i<com.size();i++)choose[i][1]=ncr2[i][1];
	for(int i=0;i<=2*n;i++)sum[0][i]=1;
	for(int i=0;i<=2*n;i++)sum[i][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<com.size();j++){
			if(com[j]>v[i].f&&com[j]<=v[i].s){
				if(choose[j][1]==1)dp[i][j]=sum[i-1][j-1];
				else{
					int cnt=0;
					for(int back=i;back>=1;back--){
						if(com[j]>v[back].f&&com[j]<=v[back].s){
							cnt++;
							dp[i][j]=(dp[i][j]+(sum[back-1][j-1]*get(j,cnt))%mod)%mod;
						}
					}
				}
			}
			sum[i][j]=((dp[i][j]+(sum[i-1][j]+sum[i][j-1])%mod)%mod-sum[i-1][j-1]+mod)%mod;
		}
	}
	out(sum[n][com.size()-1]-1);
}
/*
*/

Compilation message (stderr)

boat.cpp: In function 'int32_t main()':
boat.cpp:118:15: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |  for(int i=1;i<com.size();i++){
      |              ~^~~~~~~~~~~
boat.cpp:123:15: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |  for(int i=1;i<com.size();i++)for(int j=2;j<=n;j++)choose[i][j]=-1;
      |              ~^~~~~~~~~~~
boat.cpp:124:15: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |  for(int i=1;i<com.size();i++)choose[i][1]=ncr2[i][1];
      |              ~^~~~~~~~~~~
boat.cpp:128:16: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |   for(int j=1;j<com.size();j++){
      |               ~^~~~~~~~~~~

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