Typical DP Contest

Submission #5887335

Source codeソースコード

#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

Task問題 K - ターゲット
User nameユーザ名 loupbita
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 5
Source lengthソースコード長 1477 Byte
File nameファイル名
Exec time実行時間 92 ms
Memory usageメモリ使用量 1408 KB

Test case

Set

Set name Score得点 / Max score Cases
All 5 / 5 00,01,02,03,04,05,06,07,90,91

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
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