TIOJ 1406 魚 FISH

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define INT64 long long
using namespace std;

int n;
INT64 x[100005], y[100005];

bool check(INT64 t){
    INT64 now = y[0] - t;
    for (int i = 1; i < n; ++i){
        if(now > x[i] - x[i - 1])
            now = y[i] - t + now - x[i] + x[i - 1];
        else if(now < 0)
            now = y[i] - t + now + x[i - 1] - x[i];
        else
            now = y[i] - t;
    }
    if(now >= 0)
        return true;
    return false;
}

int main(){
    while(scanf("%d",&n) != EOF ){
        INT64 r = 0, l = 0;
        for (int i = 0; i < n; ++i){
            scanf("%lld %lld",&x[i],&y[i]);
            if(y[i] > r)
                r = y[i];
        }
        while(l < r){
            INT64 mid = (l+r)/2 + 1;
            if(check(mid))
                l = mid;
            else
                r = mid - 1;
        }
        printf("%lld\n", l);
    }
}