Submission #533828

#	Time	Username	Problem	Language	Result	Execution time	Memory
533828		new_acc	Boat (APIO16_boat)	C++14	0 / 100	329 ms	10216 KiB

boat

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=5e2+10;
const ll mod=1e9+7;
struct st{
	int a,b,dl;
};
st pw[N*2];
ll dp[N][N*2];
ll dp2[N*2][N];
pair<int,int>w[N];
ll sil[N],sp[N][N*2];
ll power(ll n,ll k){
	ll res=1;
	while(k>0){
		if(k&1) (res*=n)%=mod;
		k>>=1;
		(n*=n)%=mod;
	}
	return res;
}
void solve(){
	int n;
	cin>>n;
	vi v;
	for(int i=1;i<=n;i++){
		cin>>w[i].fi>>w[i].se;
		v.push_back(w[i].fi),v.push_back(w[i].se+1);
	}
	sort(v.begin(),v.end());
	int l=0;
	for(int i=0;i<v.size()-1;i++){
		if(v[i]==v[i+1]) continue;
		st pom;
		pom.a=v[i],pom.b=v[i+1]-1,pom.dl=(pom.b-pom.a+1);
		pw[++l]=pom;
	}
	sil[0]=1;
	for(int i=1;i<=n;i++) (sil[i]=sil[i-1]*(ll)i)%=mod;
	for(int i=1;i<=l;i++){
		for(int j=1;j<=min(pw[i].dl,n);j++){
			ll curr=1;
			for(int k=pw[i].dl;k>=pw[i].dl-j+1;k--) (curr*=(ll)k)%=mod;
			dp2[i][j]=(dp2[i][j-1]+(curr*power(sil[j],mod-2)%mod))%mod;
		}
	}
	ll res=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=l;j++){
			if(pw[j].b<w[i].fi or pw[j].a>w[i].se) continue;
			dp[i][j]=pw[j].dl;
			int il=1;
			for(int k=i-1;k>=1;k--){
				(dp[i][j]+=sp[k][j-1]*dp2[j][il])%=mod;
				if(pw[j].a>=w[k].fi and pw[j].b<=w[k].se){
					il++;
					(dp[i][j]+=dp2[j][il])%=mod;
				}
			}
			res+=dp[i][j];
		}
		for(int j=1;j<=l;j++) sp[i][j]=(sp[i][j-1]+dp[i][j])%mod;
	}
	cout<<res<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Compilation message (stderr)

boat.cpp: In function 'void solve()':
boat.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i=0;i<v.size()-1;i++){
      |              ~^~~~~~~~~~~

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