TUMSO18: Sneaky Getaway

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

typedef long long lli;

const int N = 1e5;

lli qsum[N + 1];

int main(){

    int nDay, tr;
    scanf("%d%d", &nDay, &tr);
    tr /= 2;
    for(int i = 1; i <= nDay; ++i){
        scanf("%d", &qsum[i]);
        qsum[i] = qsum[i] - tr + qsum[i - 1];
    }
    vector<lli> connect(1, 0);
    int dp = 0;
    for(int i = 1; i <= nDay; ++i){
        if(qsum[i] <= 0){
            continue;
        }
        int idx = lower_bound(connect.begin(), connect.end(), qsum[i]) - connect.begin();
        if(idx == (int)connect.size()){
            connect.push_back(0);
        }
        dp = idx;
        connect[idx] = qsum[i];
    }
    cout << dp;

    return 0;
}