2019-08-30 13:50:49 C++

C++

Copy Copied! Full
#include <bits/stdc++.h> using namespace std; #define ALL(A) (A).begin(),(A).end() #define ll long long int main(void){ int N; cin >> N; vector<pair<int,int>> p(N); for(int i=0;i<N;i++){ int w,h; cin >> w >> h; p[i].first = w; p[i].second= -h; } sort(ALL(p)); p.erase(std::unique(p.begin(), p.end()), p.end()); for(int i=0;i<N;i++)p[i].second *=-1; /* cout << endl; for(int i=0;i<N;i++){ cout << p[i].first << " " << p[i].second << endl; } */ int inf = 1e9 + 7; vector<int> dp(100005,inf); dp[0] = 0; for(int i=0;i<N;i++){ *upper_bound(ALL(dp),p[i].second) = p[i].second; //dp[1] := 長さが1のやつの最小値が5 } cout<< lower_bound(ALL(dp),inf)-dp.begin() - 1 << endl; }
RECOMMEND