oj.uz

답안 #203915

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
203915 2020-02-23T02:43:49 Z Segtree Boat (APIO16_boat) C++14
0 / 100
 2000 ms 29816 KB 
#include<iostream>
#include<algorithm>
#include<vector>
#include<unordered_map>
using namespace std;
typedef long long ll;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define mul(a,b) a=a*b%mod
#define N 510
ll po(ll x,ll y){
	ll res=1;
	for(;y;y>>=1){
		if(y&1)mul(res,x);
		x=x*x%mod;
	}
	return res;
}
ll inv[N];
unordered_map<ll,ll> C[N];
void calcc(ll l){
	ll res=1;
	C[0][l]=1;
	for(ll i=1;i<N;i++){
		mul(res,(l+1LL-i));
		mul(res,inv[i]);
		if(i>l)res=0;
		C[i][l]=res;
	}
}
unordered_map<ll,ll> f[N];
void initf(ll l,ll m){
	ll res=0;
	for(int i=1;i<=m;i++){
		mad(res,C[i][l]*C[i-1][m-1]);
	}
	f[m][l]=res;
}

ll n,a[N],b[N];
ll rui[2*N][N];
vector<ll> xs;
ll edge(ll j,ll i,ll ii){
	ll m=rui[j][ii]-rui[j][i];
	/*for(int k=i;k<ii;k++){
		if(a[k]<=j&&j<b[k])m++;
	}*/
	//cout<<"edge("<<j<<","<<i<<","<<ii<<")="<<f[m][xs[j+1]-xs[j]]<<endl;
	//cout<<"l="<<xs[j+1]-xs[j]<<", m="<<m<<endl;
	return f[m][xs[j+1]-xs[j]];
}

ll dp[N][2*N];
int main(){
	for(int i=1;i<N;i++)inv[i]=po(i,mod-2);
	cin>>n;
	a[0]=b[0]=0;
	for(int i=1;i<=n;i++){
		cin>>a[i]>>b[i];
	}
	a[n+1]=2e9,b[n+1]=2e9;
	for(int i=0;i<=n+1;i++){
		b[i]++;
		xs.push_back(a[i]);
		xs.push_back(b[i]);
	}
	sort(all(xs));
	xs.erase(unique(all(xs)),xs.end());
	for(int i=0;i<=n+1;i++){
		a[i]=lower_bound(all(xs),a[i])-xs.begin();
		b[i]=lower_bound(all(xs),b[i])-xs.begin();
	}
	rep(i,N)calcc(i);
	for(int i=0;i<xs.size()-1;i++){
		calcc(xs[i+1]-xs[i]);
		for(int m=1;m<N;m++)initf(xs[i+1]-xs[i],m);
	}
	rep(j,xs.size()-1){
		rui[j][0]=0;
		for(int i=0;i<=n+1;i++){
			rui[j][i+1]=rui[j][i]+(a[i]<=j&&j<b[i]);
		}
	}
	for(int i=0;i<=n+1;i++)rep(j,xs.size()-1)dp[i][j]=0;
	dp[0][0]=1;
	for(int ii=1;ii<=n+1;ii++){
		for(int jj=a[ii];jj<b[ii];jj++){
			for(int i=0;i<ii;i++)for(int j=0;j<jj;j++){
				mad(dp[ii][jj],dp[i][j]*edge(j,i,ii));
			}
			//cout<<"dp["<<ii<<"]["<<jj<<"]="<<dp[ii][jj]<<endl;
		}
	}
	ll ans=dp[n+1][a[n+1]]+mod-1; ans%=mod;
	cout<<ans<<endl;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:78:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<xs.size()-1;i++){
              ~^~~~~~~~~~~~
boat.cpp:10:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for(int i=0;i<n;i++)
boat.cpp:82:6:
  rep(j,xs.size()-1){
      ~~~~~~~~~~~~~             
boat.cpp:82:2: note: in expansion of macro 'rep'
  rep(j,xs.size()-1){
  ^~~
boat.cpp:10:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,n) for(int i=0;i<n;i++)
boat.cpp:88:29:
  for(int i=0;i<=n+1;i++)rep(j,xs.size()-1)dp[i][j]=0;
                             ~~~~~~~~~~~~~
boat.cpp:88:25: note: in expansion of macro 'rep'
  for(int i=0;i<=n+1;i++)rep(j,xs.size()-1)dp[i][j]=0;
                         ^~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2099 ms 29816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2099 ms 29816 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1398 ms 24060 KB Output is correct
2 Correct 1306 ms 24044 KB Output is correct
3 Correct 1353 ms 24056 KB Output is correct
4 Correct 1410 ms 24056 KB Output is correct
5 Correct 1463 ms 24212 KB Output is correct
6 Correct 1961 ms 24056 KB Output is correct
7 Execution timed out 2037 ms 24312 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2099 ms 29816 KB Time limit exceeded
2 Halted 0 ms 0 KB -