Hiker Safety

#include <iostream>
#include <vector>
using namespace std;
int B;
int P;
int K;
int d[1010];
int A[1010];
int V[1010];
vector<int> ans;

int dp[1010][1010];
bool u[1010][1010];

int f(int a, int b){
  if (u[a][b])  return dp[a][b];
  u[a][b]=1;
  
  dp[a][b]=d[b]-d[a];
  if (dp[a][b]>B) dp[a][b]=-1;
  
  if (b==P) dp[a][b]=1222333444;
  
  if (b==P || a==b) return dp[a][b];
  
  dp[a][b]=min(dp[a][b], max(f(a+1, b), f(a, b+1)));
  return dp[a][b];
}

void move(int a){
  V[a]++;
  ans.push_back(a+1);
}

void f(int a){
  if (a==0){
    if (V[a]!=P-1) move(a);
    return;
  }
  while (1){
    if (V[a]!=P-1 && f(V[a-1], V[a]+1)>=max(A[a], A[a-1])) {
      move(a);
      if (V[a]!=P-1) return;
    }else if (V[a-1]!=P-1 && (V[a]==P-1 || f(V[a-1]+1, V[a])>=max(A[a], A[a-1]))){
      f(a-1);
    }else if (V[a-1]!=P-1){
      cout << "impossible\n";
      exit(0);
    }else{
      return;
    }
  }
}

int main(){
  cin >> B;
  cin >> P;
  for (int i=0; i<P; ++i) cin >> d[i]; d[P]=d[P-1];
  cin >> K;
  for (int i=0; i<K; ++i){
    cin >> A[i];
    cin >> V[i]; --V[i];
  }
  while (V[0]!=P-1) f(K-1);
  for (auto a : ans) cout << a << " "; cout << "\n";
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED