Submission #11379110
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define ALL(x) x.begin(),x.end() #define rep(i,n) for(int i=0;i<(n);i++) #define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl; #define INF 1000000000 #define mod 1000000007 using ll=long long; const ll LINF=1001002003004005006ll; int dx[]={1,0,-1,0}; int dy[]={0,1,0,-1}; ll gcd(ll a,ll b){return b?gcd(b,a%b):a;} template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;} template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;} template<typename T> int LIS(const vector<T> &a){ vector<T> lis; for(auto &p:a){ typename vector<T>::iterator it; //同値許容しない(狭義単調増加) it=lower_bound(begin(lis),end(lis),p); //同値許容(広義単調増加) // it=upper_bound(begin(lis),end(lis),p); if(end(lis)==it) lis.push_back(p); else *it=p; } return int(lis.size()); } signed main(){ cin.tie(0); ios::sync_with_stdio(0); int n;cin>>n; vector<pair<ll,ll>> v(n); rep(i,n){ ll x,r;cin>>x>>r; v[i]=make_pair(x-r,x+r); } sort(ALL(v)); reverse(ALL(v)); vector<ll> a(n); rep(i,n) a[i]=v[i].second; cout<<LIS(a)<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | K - ターゲット |
User | mugen1337 |
Language | C++14 (GCC 5.4.1) |
Score | 5 |
Code Size | 1335 Byte |
Status | AC |
Exec Time | 32 ms |
Memory | 3832 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 | 32 ms | 2560 KB |
01 | AC | 31 ms | 2560 KB |
02 | AC | 32 ms | 2560 KB |
03 | AC | 29 ms | 2560 KB |
04 | AC | 29 ms | 2560 KB |
05 | AC | 29 ms | 2560 KB |
06 | AC | 21 ms | 3832 KB |
07 | AC | 17 ms | 2560 KB |
90 | AC | 1 ms | 256 KB |
91 | AC | 1 ms | 256 KB |