oj.uz

Submission #268710

# Submission time Handle Problem Language Result Execution time Memory
268710 2020-08-16T20:05:42 Z test2 Boat (APIO16_boat) C++14
0 / 100
 52 ms 45944 KB 
#include<bits/stdc++.h>

#define I inline void 

using ll = long long ; 
using ld = long double ; 

using namespace std ; 

const int N = 5000 + 7 , mod = 1e9 + 7 ; 

// how interesting!

int n; 

ll ans ; 
map<int , int > used ; 
set<pair<int , int> > st ; 
ll sz[N] ;
vector<pair<int , int> > v ; 
ll f[N] ; 

I add(int u , int v){
	while(u <=v && used[u])u++ ; 
	while(v>=u&&used[v])v-- ; 

	if(u <=v){
		used[u] = used[v] = 1; 
		st.insert({u , v}) ; 
	}
}

vector<int> onepiece[N * 10] ; 
std::vector<int> szs[N * 10];

ll dp[N][505] ; 

ll mul(ll a , ll b){
	return (1ll * a * b) %mod ; 
}

ll faspow(ll x , ll y){
	if(!y)return 1ll ; 
	ll ret = faspow(x , y/2) ; 
	ret = (1ll * ret * ret ) %mod ;
	if(y&1)ret = 1ll * ret * x %mod ; 
	return ret ; 
}

ll ncr(ll x , ll y){
	ll ret = mul(f[x] , faspow(f[y] , mod -2)) ; 
	ret = mul(ret , faspow(f[x - y] , mod-2)) ; 
}

ll solve(int i , int j){
	if(dp[i][j]!=-1)
		return dp[i][j] ; 
	if(i == (int) st.size())
		return 1; 
	ll ret = solve(i+1 , j ) ; 

	int pos = 0 ;
	ll add = 0ll ; 
	sort(onepiece[i].begin() , onepiece[i].end()) ; 
	int k = 0 ; 
	for(auto u : onepiece[i]){
		if(u > j){
			if( k +1 <= sz[i])
				add = (add + ncr(sz[i] , min((int) sz[i] , ++ k ) )  )  %mod ; 
						ll plls = mul( add , solve(i+1,  u) ) ; 
			ret = (ret + plls ) %mod  ; 
		}
		pos ++ ; 
	}
	return dp[i][j] = ret ; 
}

ll conts[N] ; 

int main(){	
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; 
	memset(dp , -1 , sizeof dp) ; 

	f[0] = 1ll ; 
	for(int i =1 ; i < N ;i++){
		f[i]= mul(f[i-1] , i) ; 
	}

	//freopen("in.in" , "r" , stdin) ;  
	cin >> n; 
	set<int> ev ; 

	for(int i = 0 ;i < n;i++){
		int x , y ; 
		cin >> x >> y ; 
		ev.insert(x) ; 
		ev.insert(y) ; 
		used[x] = used[y] = 1; 
		st.insert({x , x}) ; 
		st.insert({y , y}) ;
		//for(int j =x ;j <= y ;j ++)
		//	st.push_back({j , j})  ; 
		v.push_back({x , y}) ; 
	}
	
	int l = 0 ; 
	for(auto u : ev){
		if(l){
			add(l+1 , u - 1) ; 
		}
		l = u ; 
	}

	int pos = 0 ; 
	for(auto u : st){ 

		for(int j = 0 ;j < n; j++){
			if(  u.first>= v[j].first &&  u.second <= v[j].second ){
				onepiece[pos].push_back(j + 1) ; 
				szs[pos].push_back( u.second - u.first +1 ) ; 

				sz[pos] += u.second - u.first + 1ll ;
				conts[j] +=  u.second -  u.first + 1 ; 
			}
		}
		sz[pos] = u.second - u.first + 1 ; 
		pos ++ ; 
	}
		
	cout<< (mod + solve(0 ,  0 ) -1 ) %mod ; 
	return 0 ; 
}

Compilation message

boat.cpp: In function 'll ncr(ll, ll)':
boat.cpp:53:1: warning: no return statement in function returning non-void [-Wreturn-type]
   53 | }
      | ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 45944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 45944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 45 ms 45944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 52 ms 45944 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -