Submission #5627394
Source Code Expand
#define _USE_MATH_DEFINES #include<iostream> #include<string> #include<queue> #include<cmath> #include<map> #include<set> #include<list> #include<iomanip> #include<vector> #include<random> #include<functional> #include<algorithm> #include<stack> #include<cstdio> #include<bitset> #include<unordered_map> #include<climits> #include<fstream> using namespace std; ///////////////////library zone!!!!!!!!!!!!!!!!!!!!!!!!!!!! typedef long long ll; typedef long double ld; #define all(a) (a).begin(),(a).end() #define EPS (1e-5) #define bit(n,k) ((n>>k)&1) const ll Mod = 1000000007; const ll mod = 998244353; struct H { ll x, y; bool operator<(const H& b) const { if (x != b.x) return x < b.x; return y < b.y; } bool operator>(const H & b) const { if (x != b.x) return x > b.x; return y > b.y; } bool operator==(const H & b) const { return x == b.x && y == b.y; } bool operator!=(const H & b) const { return (*this) != b; } }; struct P { ll pos, cost; bool operator<(const P& b) const { return cost < b.cost; } bool operator>(const P& b) const { return cost > b.cost; } }; struct B { ll to, cost; }; struct E { ll from, to, cost; bool operator<(const E& b) const { return cost < b.cost; } bool operator>(const E& b) const { return cost > b.cost; } }; template<typename T, typename U> void chmin(T & a, U b) { if (a > b) a = b; } template<typename T, typename U> void chmax(T & a, U b) { if (a < b) a = b; } template<typename T> T max_0(T a) { if (a < 0) return 0; return a; } template<typename T> T min_0(T a) { if (a > 0) return 0; return a; } ll read() { ll u; ll k = scanf("%lld", &u); return u; } ll gcd(ll i, ll j) { if (i > j) swap(i, j); if (i == 0) return j; return gcd(j % i, i); } ll mod_pow(ll x, ll n, ll p) { ll res = 1; while (n > 0) { if (n & 1) res = res * x % p; x = x * x % p; n >>= 1; } return res; }//x^n%p const ll Inf = 3023372036854775807; const int inf = 1500000000; #define int long long //---------------------------------------------------- int n; H a[200000]; H b[200000]; int dp[200000]; signed main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i].x >> a[i].y; b[i] = H{ a[i].x + a[i].y,a[i].x - a[i].y }; } sort(b, b + n); for (int i = 1; i <= n; i++) dp[i] = Inf; dp[0] = -Inf; int ans = 0; for (int i = 0; i < n; i++) { int k = lower_bound(dp, dp + n + 1, -b[i].y) - dp; dp[k] = -b[i].y; ans = max(ans, k); } cout << ans << endl; }
Submission Info
Submission Time | |
---|---|
Task | K - ターゲット |
User | Thistle |
Language | C++14 (GCC 5.4.1) |
Score | 5 |
Code Size | 2545 Byte |
Status | AC |
Exec Time | 85 ms |
Memory | 5760 KB |
Judge Result
Set Name | All | ||
---|---|---|---|
Score / Max Score | 5 / 5 | ||
Status |
|
Set Name | Test Cases |
---|---|
All | 00, 01, 02, 03, 04, 05, 06, 07, 90, 91 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00 | AC | 85 ms | 5760 KB |
01 | AC | 85 ms | 5760 KB |
02 | AC | 85 ms | 5760 KB |
03 | AC | 68 ms | 5760 KB |
04 | AC | 68 ms | 5760 KB |
05 | AC | 68 ms | 5760 KB |
06 | AC | 52 ms | 5760 KB |
07 | AC | 48 ms | 5760 KB |
90 | AC | 1 ms | 2304 KB |
91 | AC | 1 ms | 2304 KB |