제출 #124038

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
124038		youssefbou62	Boat (APIO16_boat)	C++14	0 / 100	7 ms	3320 KiB

boat

#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
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42