Submission #6421038
Source Code Expand
#include <bits/stdc++.h> #define debug(x) cerr << #x << ": " << x << '\n'; using namespace std; using ll = long long; using P = pair<int, int>; const int INF = (int)1e9; int N; P circle[100000]; P dp[100000]; int main(void){ cin >> N; for(int i = 0; i < N; i++){ int x, r; cin >> x >> r; circle[i] = P(x-r, x+r); } sort(circle, circle + N, [](P a, P b){return (a.second==b.second) ? a.first<b.first : a.second>b.second;}); for(int i = 0; i < N; i++) dp[i] = P(INF, INF); for(int i = 0; i < N; i++){ *lower_bound(dp, dp + N, circle[i], [](P a, P b){return a.first < b.first;}) = circle[i]; } cout << lower_bound(dp, dp + N, P(INF, INF)) - dp << '\n'; return 0; }
Submission Info
Submission Time | |
---|---|
Task | K - ターゲット |
User | yna87 |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 755 Byte |
Status | WA |
Exec Time | 109 ms |
Memory | 1792 KB |
Judge Result
Set Name | All | ||||
---|---|---|---|---|---|
Score / Max Score | 0 / 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 | 108 ms | 1792 KB |
01 | AC | 108 ms | 1792 KB |
02 | AC | 109 ms | 1792 KB |
03 | WA | 82 ms | 1792 KB |
04 | WA | 84 ms | 1792 KB |
05 | WA | 83 ms | 1792 KB |
06 | AC | 60 ms | 1792 KB |
07 | AC | 57 ms | 1792 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 256 KB |