この問題は答えを二分探索することで解くことができます。

冒険開始時の強さが \(X\) のときに階層 \(N\) に到達可能ならば、冒険開始時の強さが \(X\) 以上であれば常に階層 \(N\) に到達可能です。

また、冒険開始時の強さが \(X\) のとき、高橋君が階層 \(N\) に到達できるかどうかは、実際にシミュレーションを行うことで \(O(N)\) で判定できます。

よって、階層 \(N\) に到達可能な最小強さを二分探索で求めることでこの問題は \(O(N\log K)\) で求めることができます。

実装例 (C++)

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

int main(){
  int n;
  long long s, k;
  cin >> n >> s >> k;
  vector<int> e(n);
  for(int i=0; i<n; i++) cin >> e[i];

  auto solve = [&](long long p){
    for(int i=0; i<n; i++){
      if(p < e[i]){
        return false;
      }
      p += e[i];
    }
    return true;
  };

  if(!solve(s+k)){
    cout << -1 << endl;
    return 0;
  }

  long long ok = k;
  long long ng = -1;
  while(ok - ng > 1){
    long long m = (ok + ng) / 2;
    if(solve(s+m)){
      ok = m;
    }else{
      ng = m;
    }
  }
  cout << ok << endl;
}

実装例 (Python)

N, S, K = map(int, input().split())
E = list(map(int, input().split()))

def solve(P):
  # 初期強さが P のとき階層 N に到達可能か？
  for e in E:
    if P < e:
      return False
    P += e
  return True

if not solve(S+K):
  print(-1)
  exit()

ok = K
ng = -1
while ok - ng > 1:
  m = (ok + ng) // 2
  if solve(S+m):
    ok = m
  else:
    ng = m
print(ok)