Submission #5496711


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;

const long long INF = 1LL << 60;
typedef pair<int, int> P;

int main()
{
    int N;
    cin >> N;

    vector<P> r(N);
    rep(i, N) {
        int r1, r2;
        cin >> r1 >> r2;
        r[i].first = r1 - r2;
        r[i].second = r1 + r2;
    }

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

    vector<ll> dp(N, INF);

    rep(i, N) {
        *lower_bound(dp.begin(), dp.end(), r[i].second * -1) = r[i].second * -1;
    }

    int ans = 1;

    rep(i, N) {
        if (dp[i] != INF) ans = i + 1;
        else break;
    }

    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task K - ターゲット
User wolley
Language C++14 (GCC 5.4.1)
Score 5
Code Size 938 Byte
Status AC
Exec Time 86 ms
Memory 1792 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 86 ms 1792 KB
01 AC 86 ms 1792 KB
02 AC 86 ms 1792 KB
03 AC 69 ms 1792 KB
04 AC 69 ms 1792 KB
05 AC 69 ms 1792 KB
06 AC 52 ms 1792 KB
07 AC 48 ms 1792 KB
90 AC 1 ms 256 KB
91 AC 1 ms 256 KB