#DP #PickOrLeave #Codeforces #Solved

C. Woodcutters.cpp

//http://codeforces.com/contest/545/problem/C
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;
const int MAX = (int)1e5+5;
int cache[MAX][2];
int x[MAX], h[MAX];
int n;

int maxCut(int i, bool pre) {
    if(i == n) return 0;

    int &ret = cache[i][pre];
    if(ret != -1) return ret;

    int ch1 = maxCut(i+1, 0); // no cut

    // cut to the left
    int ch2 = 0;
    if(i != 0) {
        int l = x[i] - x[i-1];
        if(pre) l -= h[i-1];
        if(l > h[i])
            ch2 = maxCut(i+1, 0) + 1;
    } else {
        ch2 = maxCut(i+1, 0) + 1;
    }

    // cut to the right
    int ch3 = 0;
    if(i != n-1) {
        int l = x[i+1] - x[i];
        if(l > h[i])
            ch3 = maxCut(i+1, 1) + 1;
    } else {
        ch3 = maxCut(i+1, 1) + 1;
    }

    return ret = max(max(ch1, ch2), ch3);
}

void traceOperations(int i, bool pre) {
    if(i == n) return ;

    int ch1 = maxCut(i+1, 0); // no cut

    // cut to the left
    int ch2 = 0;
    if(i != 0) {
        int l = x[i] - x[i-1];
        if(pre) l - h[i-1];
        if(l > h[i])
            ch2 = maxCut(i+1, 0) + 1;
    } else {
        ch2 = maxCut(i+1, 0) + 1;
    }

    // cut to the right
    int ch3 = 0;
    if(i != n-1) {
        int l = x[i+1] - x[i];
        if(l > h[i])
            ch3 = maxCut(i+1, 1) + 1;
    } else {
        ch3 = maxCut(i+1, 1) + 1;
    }

    int opt = maxCut(i, pre);
    if(opt == ch1) {
        traceOperations(i+1, 0);
    } else if(opt == ch2) {
        cout << x[i] << endl;
        traceOperations(i+1, 0);
    } else {
        cout << x[i] << endl;
        traceOperations(i+1, 1);
    }
}

int main() {
    cin>>n;
    lp(i, n) cin>>x[i]>>h[i];
    clr(cache, -1);
    cout << maxCut(0, 0) << endl;
    //traceOperations(0, 0);
}