|
|
back to boardI am getting a tle on my dp algo ontest case !11 #include "bits/stdc++.h" using namespace std; vector<pair<int,int> > v; int n; vector<int> v1; int dp[100001]; int recurse(int temp){
if(dp[temp] != -1) return dp[temp];
int search = v[temp].second; int lower = lower_bound(v1.begin(), v1.end(), search) - v1.begin(); // cout << search << " " << lower << "**"; int max1 = 0; for(int i = lower; i < v1.size(); i++){ // cout << v1[i] << "/" << search << "\n"; if(v1[i] - search >= 1){ max1 = max(max1, recurse(i)+1); } } return dp[temp] = max1; } int main(int argc, char const *argv[]) { // ios::sync_with_stdio(false); scanf("%d",&n); memset(dp, -1, sizeof dp); while(n--){ int st, en; scanf("%d%d",&st,&en); v.push_back(make_pair(st, en)); } sort(v.begin(), v.end()); for(int i = 0; i < v.size(); i++){ v1.push_back(v[i].first); // cout << v[i].first << " " << v[i].second << "\n"; } int max1 = 0; for(int i = 0; i < v.size(); i++) max1 = max(max1, recurse(i)+1); printf("%d",max1); return 0; } |
|
|