Submission #5887335


Source Code Expand

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
 
#define _USE_MATH_DEFINES
#define mp       make_pair
#define pb       push_back
#define fst      first
#define snd      second
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;

const int INF=1<<29;
const double EPS=1e-9;

const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};


int main()
{
    int N; cin >> N;
    int x, r;
    vector<pii> lr(N);
    rep(i,N) {
        cin >> x >> r;
        lr[i] = mp(x-r, x+r);
    }

    sort(lr.begin(), lr.end());

    vi dp(N+1, -INF);
    dp[0] = INF;

    int ans = 0;
    rep(i,N) {
        for(int j = ans; j >= 0; j--) {
            if(lr[i].second < dp[j]) {
                dp[j+1] = max(lr[i].second, dp[j+1]);
                ans = max(j+1, ans);
                break;
            }
        }
    }

    cout << ans << endl;
    return 0;

    return 0;
}

Submission Info

Submission Time
Task K - ターゲット
User loupbita
Language C++14 (GCC 5.4.1)
Score 5
Code Size 1477 Byte
Status AC
Exec Time 92 ms
Memory 1408 KB

Judge Result

Set Name All
Score / Max Score 5 / 5
Status
AC × 10
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 07, 90, 91
Case Name Status Exec Time Memory
00 AC 92 ms 1408 KB
01 AC 91 ms 1408 KB
02 AC 92 ms 1408 KB
03 AC 75 ms 1408 KB
04 AC 74 ms 1408 KB
05 AC 75 ms 1408 KB
06 AC 47 ms 1408 KB
07 AC 48 ms 1408 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB