Submission #1798819
Source Code Expand
#include <bits/stdc++.h> using namespace std; using i64=int64_t; #define rep(i,x,y) for(i64 i=i64(x),i##_max_for_repmacro=i64(y); i<i##_max_for_repmacro; ++i) #define debug(x) #x << "=" << (x) #ifdef DEBUG #define _GLIBCXX_DEBUG #define print(x) std::cerr << debug(x) << " (L:" << __LINE__ << ")" << std::endl #else #define print(x) #endif const int inf=1.01e9; const i64 inf64=4.01e18; const double eps=1e-9; template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){ os << "["; for (const auto &v : vec) { os << v << ","; } os << "]"; return os; } void solve(){ int N; cin >> N; vector<pair<int,int>> xr(N); rep(i,0,N) cin >> xr[i].first >> xr[i].second; sort(begin(xr),end(xr),[](pair<int,int> &a,pair<int,int> &b){ return a.first-a.second<b.first-b.second; }); vector<int> ls(N); rep(i,0,N) ls[i]=xr[i].first-xr[i].second; static int dp[100000]; static bool done[1000000]; function<int(int)> rec=[&](int i){ int& res=dp[i]; if(done[i]) return res; done[i]=true; res=1; int l=xr[i].first-xr[i].second,r=xr[i].first+xr[i].second; for(;;){ int j=upper_bound(begin(ls),end(ls),l)-begin(ls); if(j==N or ls[j]>=r) break; if(xr[j].first+xr[j].second>=r){ l=ls[j]; continue; } res=max(res,rec(j)+1); l=xr[j].first+xr[j].second; } return res; }; int ans=0; rep(i,0,N) ans=max(ans,rec(i)); cout << ans << endl; } int main(){ std::cin.tie(0); std::ios::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(16); solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | K - ターゲット |
User | walkre |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1845 Byte |
Status | WA |
Exec Time | 531 ms |
Memory | 8192 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 | 522 ms | 1920 KB |
01 | WA | 526 ms | 1920 KB |
02 | WA | 531 ms | 1920 KB |
03 | WA | 490 ms | 1920 KB |
04 | WA | 485 ms | 1920 KB |
05 | WA | 489 ms | 1920 KB |
06 | AC | 28 ms | 8192 KB |
07 | AC | 27 ms | 1920 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 256 KB |