Submission #403429

#	Time	Username	Problem	Language	Result	Execution time	Memory
403429		myrcella	Boat (APIO16_boat)	C++17	100 / 100	1133 ms	8420 KiB

boat

//by szh
#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}

const int maxn=1e3+10;

int n;
int f[2][maxn][maxn];
int a[maxn],b[maxn];
map <int,int> mp;
int pm[maxn];
ll inv[maxn];
int sum[maxn];

int main() {
//	freopen("input.txt","r",stdin);	
	std::ios::sync_with_stdio(false);cin.tie();
	cin>>n;
	rep(i,1,maxn) inv[i]=p0w(i,mod-2);
	mp[0]=1;
	rep(i,1,n+1) cin>>a[i]>>b[i],a[i]--,mp[a[i]]=mp[b[i]]=1;
	int tot=0;
	for (auto &it:mp) it.se=tot,pm[tot++]=it.fi;
	int lst=0,cur=1;
	f[lst][0][0]=1;
	rep(i,1,n+1) {
		memset(sum,0,sizeof(sum));
		memset(f[cur],0,sizeof(f[cur]));
		rep(j,0,tot) 
			rep(k,0,i) {
				if (f[lst][j][k]==0) continue;
				//doesn't choose
				inc(f[cur][j][k],f[lst][j][k]); 
				inc(sum[j],f[lst][j][k]);
//				cout<<i-1<<" "<<j<<" "<<k<<" "<<f[lst][j][k]<<endl;
			}
//		debug(sum[0]),debug(sum[1]),debug(sum[2]);
		rep(j,mp[a[i]]+1,mp[b[i]]+1) {
			rep(k,0,i) {	
				//choose from the same segment
				if (pm[j]-pm[j-1]>=k+1) inc(f[cur][j][k+1],1ll*f[lst][j][k]*(pm[j]-pm[j-1]-k)%mod*inv[k+1]%mod);
			}
		}
		rep(j,1,tot) inc(sum[j],sum[j-1]);
//		debug(sum[1]),debug(sum[2]),debug(sum[3]);
//		debug(a[i]),debug(b[i]),debug(mp[a[i]]),debug(mp[b[i]]);
		rep(j,mp[a[i]],mp[b[i]]) {
			//start from a new segment
			inc(f[cur][j+1][1],1ll*sum[j]*(pm[j+1]-pm[j])%mod);
		}
		
		swap(lst,cur);
	}
	int ans=0;
	rep(i,1,tot)
		rep(j,1,n+1) inc(ans,f[lst][i][j]);
	cout<<ans<<endl;
	return 0;
}

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