oj.uz

Submission #533838

# Submission time Handle Problem Language Result Execution time Memory
533838 2022-03-07T11:51:55 Z new_acc Boat (APIO16_boat) C++14
0 / 100
 705 ms 14472 KB 
#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];
ll dp3[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<=n;j++){
			ll curr=1;
			for(int k=pw[i].dl;k>=pw[i].dl-j+1;k--) (curr*=(ll)k)%=mod;
			if(j>pw[i].dl) curr=0;
			dp2[i][j]=(dp2[i][j-1]+(curr*power(sil[j],mod-2)%mod))%mod;
			dp3[i][j]=(curr*power(sil[j],mod-2))%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]+=dp3[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

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

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 705 ms 14472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 705 ms 14472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 2892 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 705 ms 14472 KB Output isn't correct
2 Halted 0 ms 0 KB -