Submission #5496711
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define repd(i,a,b) for (int i=(a);i<(b);i++) #define rep(i,n) repd(i,0,n) template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; } typedef long long ll; const long long INF = 1LL << 60; typedef pair<int, int> P; int main() { int N; cin >> N; vector<P> r(N); rep(i, N) { int r1, r2; cin >> r1 >> r2; r[i].first = r1 - r2; r[i].second = r1 + r2; } sort(r.begin(), r.end()); vector<ll> dp(N, INF); rep(i, N) { *lower_bound(dp.begin(), dp.end(), r[i].second * -1) = r[i].second * -1; } int ans = 1; rep(i, N) { if (dp[i] != INF) ans = i + 1; else break; } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | K - ターゲット |
User | wolley |
Language | C++14 (GCC 5.4.1) |
Score | 5 |
Code Size | 938 Byte |
Status | AC |
Exec Time | 86 ms |
Memory | 1792 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 | 86 ms | 1792 KB |
01 | AC | 86 ms | 1792 KB |
02 | AC | 86 ms | 1792 KB |
03 | AC | 69 ms | 1792 KB |
04 | AC | 69 ms | 1792 KB |
05 | AC | 69 ms | 1792 KB |
06 | AC | 52 ms | 1792 KB |
07 | AC | 48 ms | 1792 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 256 KB |