Submission #3012867
Source Code Expand
#include <iostream> #include <string> #include <queue> #include <vector> #include <set> #include <map> #include <algorithm> #include <utility> #include <iomanip> #define ll long long int #define pb push_back #define mk make_pair #define pq priority_queue using namespace std; typedef pair<int, int> P; typedef pair<ll, int> Pl; const int inf = 1e9; const ll linf = 1LL << 50; int n; ll x[100001]; ll r[100001]; vector<int> vec; int dp[100001]; bool comp(const int &a, const int &b){ if(x[a] - r[a] > x[b] - r[b] && x[a] + r[a] < x[b] + r[b])return true; return false; } bool compr(const int &a, const int &b){ return r[a] < r[b]; } int main(int argc, char const* argv[]) { cin >> n; for(int i = 0; i < n; i++){ cin >> x[i] >> r[i]; vec.pb(i); } x[n] = 0; r[n] = linf / 2; sort(vec.begin(), vec.end(), compr); fill(dp, dp + n + 1, n); for(int i = 0; i < n; i++){ *lower_bound(dp, dp + n + 1, i, comp) = i; } cout << lower_bound(dp, dp + n + 1, n, comp) - dp << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | K - ターゲット |
User | fumiphys |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1061 Byte |
Status | WA |
Exec Time | 93 ms |
Memory | 2680 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 | WA | 93 ms | 2680 KB |
01 | WA | 93 ms | 2680 KB |
02 | WA | 93 ms | 2680 KB |
03 | WA | 76 ms | 2680 KB |
04 | WA | 76 ms | 2680 KB |
05 | WA | 76 ms | 2680 KB |
06 | AC | 60 ms | 2680 KB |
07 | AC | 54 ms | 2680 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 256 KB |