oj.uz

Submission #124038

# Submission time Handle Problem Language Result Execution time Memory
124038 2019-07-02T11:59:33 Z youssefbou62 Boat (APIO16_boat) C++14
0 / 100
 7 ms 3320 KB 
#include  <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fi first
#define se second
#define all(v) v.begin(),v.end()
#define allarr(a) a , a + n
#define ll long long
#define ull unsigned long long 
#define pb push_back
#define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL)
typedef pair<int, int> pi;
typedef pair<ll,ll> pll; 
typedef pair<int,pi> trp ;
typedef vector<pi> vpi;
typedef vector<pll> vpll ;
ll _abs (ll x ) { return (x>0?x:-x); }
const int N = 505 ; 
const ll mod = 1e9+7 ; 
int dp[N][N] ;
pi a[N] ;  
ll C[N][N] ; 
int rnk[N] ; 
void  cnk (){
	C[0][0] = 1;
	for (int n = 1; n  < N ; ++n) {
    	C[n][0] = C[n][n] = 1;
    	for (int k = 1; k < n; ++k){
        	C[n][k] = (C[n - 1][k - 1] + C[n - 1][k])%mod;
        	C[n][k] %= mod ; 
		}
    }
}

int lis(int i , int prev , int n  ){
	if( i == n )return 0 ; 
	int& r  = dp[i][prev] ; 
	if( r != -1 ) return r ; 
	if( prev < rnk [i] )
	return r = max ( lis ( i + 1 , prev , n ) , 1+lis ( i + 1 , rnk[i] , n ) ) ;  
	return r = lis ( i + 1 , prev , n ) ; 
}


int main(){
	int n ; 
	cin >> n ; 
	cnk ( ) ; 
    for(int i= 0 ; i < n ; i++ ){
		cin >> a[i].fi >> a[i].fi ;
		a[i].se = i ;  
	}
	sort(a,a+n ) ; 
	for(int i = 0 ; i < n ; i++ ){
		rnk[a[i].se] = i ; 
		if( i && a[i].fi == a[i-1].fi )rnk[a[i].se] = rnk[a[i-1].se] ;
	}
	ll ans = 0 ; 
    memset ( dp , -1 , sizeof dp ) ; 
	for( int i = 0 ; i < n ;i++ ){
		int ls = lis ( i + 1 , rnk[i] , n ) ; 
        // cout << "********* i,ls "<<i <<" " << ls << "**********"<<endl; 
		for(int p = 1 ; p <= ls ; p++ ){
			ans += (C[ls][p]) % mod ; 
			ans %= mod ; 
            // cout << p+1 << " " << C[ls][p] << endl; 
		}// cout << i << " " << ls << endl;
        ans ++ ; 

	}cout << ans << endl; 
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 3320 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 3320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 3320 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 3320 KB Output isn't correct
2 Halted 0 ms 0 KB -