oj.uz

Submission #268680

# Submission time Handle Problem Language Result Execution time Memory
268680 2020-08-16T18:19:01 Z test2 Boat (APIO16_boat) C++14
0 / 100
 7 ms 4480 KB 
#include<bits/stdc++.h>

#define I inline void 

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

using namespace std ; 

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

// how interesting!

int n; 

ll ans ; 
vector<pair<int , int> > st ; 

vector<pair<int , int> > v ; 

I add(int u , int v){
	if(u <=v){
		st.push_back({u , v}) ; 
	}
}

vector<int> onepiece[N] ; 

int dp[N][N] ; 

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

	for(auto u : onepiece[i]){
		if(u > j){
			ret = (ret + solve(i+1 , u)) ; 
		}
	}
	return dp[i][j] = ret ; 
}


int main(){	
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; 
	memset(dp , -1 , sizeof dp) ; 
	//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) ; 
		st.push_back({x , x}) ; 
		st.push_back({y , y}) ;
		v.push_back({x , y}) ; 
	}

	int l = 0 ; 
	for(auto u : ev){
		if(l){
			add(l+1 , u - 1) ; 
		}
		l = u ; 
	}

	sort(st.begin() , st.end()) ; 
	st.resize( unique(st.begin() , st.end()) - st.begin()) ; 

	for(int i = 0 ;i < (int) st.size() ; i++){
		for(int j = 0 ;j < n; j++){
			if( st[i].first>= v[j].first && st[i].second <= v[j].second ){
				onepiece[i].push_back(j + 1) ; 
			}
		}
	}
	cout<< (mod + solve(0 ,  0 ) -1 ) %mod ; 
	return 0 ; 
}

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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