oj.uz

Submission #270545

# Submission time Handle Problem Language Result Execution time Memory
270545 2020-08-17T18:00:18 Z test2 Boat (APIO16_boat) C++14
0 / 100
 25 ms 10104 KB 
#include<bits/stdc++.h>

#define I inline void 

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

using namespace std ; 

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

// how interesting!

int n , m; 
vector<int> lst ; 
int L[N] , R[N] , S[N] ; 
int dp[001][501] ;

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 inv[N] ; 

int main(){	
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; 
	//freopen("in.in" , "r" , stdin) ;  
	inv[1] = 1ll ; 
	for(int i = 2; i < N; i++) inv[i] = (mod/i) * (mod-inv[mod%i]) % mod;



	cin >> n ; 
	for(int i = 1 ;i <= n;i++){
		cin >> L[i] >> R[i] ; 
		R[i] ++ ;
		lst.push_back(L[i]) ; 
		lst.push_back(R[i]) ;
	}
	sort(lst.begin() , lst.end()) ; 
	lst.resize(unique(lst.begin() , lst.end()) - lst.begin()) ; 


	for(int i = 1 ;i <= n ;i++){
		L[i] = lower_bound(lst.begin() , lst.end() , L[i]) - lst.begin() + 1; 
		R[i] = lower_bound(lst.begin() , lst.end() , R[i]) - lst.begin() + 1;
	}

	int w = lst.size() ; 
	for(int i = 1 ;i < w ;i++){
		S[i] = lst[i] - lst[i-1] ; 
	}

	dp[0][0] = 1ll ;
	for(int i = 1 ;i < w ;i++){
		dp[i][0] = 1ll ; 


		for(int j = 1 ;j <=n ;j++){
			int count = 1; 
			ll mul = S[i] ; 

			dp[i][j] = dp[i-1][j] ; 

			if(i < L[j] || i >= R[j])
				continue ; 

			for(int k = j -1 ; k >= 0 ; k --){
				dp[i][j] = (dp[i][j] + (mul * dp[i-1][k]) %mod  ) %mod ; 
				if(L[k] <= i && R[k] > i){
					mul = 1ll * mul * (S[i] + count) %mod ; 
					mul = 1ll * mul * inv[count +1] %mod ; 
					count ++ ;
				}	
			}
		}
	}


	ll ans = 0ll ; 
	for(int i = 1 ; i<=n ;i++){
		ans = (ans + dp[w-1][i]) %mod ; 
	}
	cout<< ans ; 
	return 0 ; 
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:61:7: warning: array subscript 1 is above array bounds of 'int [1][501]' [-Warray-bounds]
   61 |   dp[i][0] = 1ll ;
      |   ~~~~^
boat.cpp:17:5: note: while referencing 'dp'
   17 | int dp[001][501] ;
      |     ^~
boat.cpp:68:8: warning: array subscript 1 is above array bounds of 'int [1][501]' [-Warray-bounds]
   68 |    dp[i][j] = dp[i-1][j] ;
      |    ~~~~^
boat.cpp:17:5: note: while referencing 'dp'
   17 | int dp[001][501] ;
      |     ^~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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