Hiker Safety

#include <bits/stdc++.h>
using namespace std;
int B;
int P;
int K;
int d[1111];
int dp[1111][1111];
int A[1111];
int V[1111];
int A2[1111];
int V2[1111];
vector<int> ans;
int f(int a, int b) {
	if(dp[a][b] != -1) return dp[a][b];
	if(b == P-1) {
		dp[a][b] = 1e9;
		return dp[a][b];
	}
	if(a >= b) {
		dp[a][b] = -2;
		return dp[a][b];
	}
	dp[a][b] = d[b] - d[a]; //personal space
	if(dp[a][b] <= 0) dp[a][b] = -2;
	int q = -1e9;
	if(abs(d[a+1]-d[b]) <= B) {
 
		q = max(f(a+1, b), q);
	}
	if(abs(d[a]-d[b+1]) <= B) {
		q = max(f(a, b+1), q);
	}
	dp[a][b] = min(q, dp[a][b]);
	if(abs(d[a]-d[b]) > B) dp[a][b] = -2;
	return dp[a][b];
}
void g(int x) {
	if(x == 0) {
		if(V[x] == P-1) return;
		ans.push_back(x);
		V[x]++;
		return;
	}
	while(dp[V[x-1]+1][V[x]] >= max(A[x], A[x-1])) {
		g(x-1);
		if(V[x-1] == P-1) return;
	}
	if(V[x] == P-1) {
		return;
	}
	if(dp[V[x-1]][V[x]+1] >= max(A[x], A[x-1])) {
		ans.push_back(x);
		V[x]++;
		return;
	}
	cout<<"impossible\n";
	exit(0);
}
int main(){
  cin >> B;
  cin >> P;
  for (int i=0; i<P; ++i) cin >> d[i];
  cin >> K;
  for (int i=0; i<K; ++i){
    cin >> A[i] >> V[i];
    --V[i];
    V2[i] = V[i];
  }
  memset(dp, -1, sizeof dp);
  for(int i = 0; i < P; ++i) {
	  for(int j = 0; j < P; ++j) {
		  if(dp[i][j] == -1) f(i, j);
	  }
  }
  for(int i = K-1; i >= 0; --i) {
	  while(V[i] != P-1) {
		  g(i);
	  }
  }
  for(auto x: ans) {
	  V2[x]++;
	  if (x+1<K && V2[x+1]!=P-1){
		  int dd=d[V2[x+1]]-d[V2[x]];
		  if (dd<max(A[x],A[x+1]) || dd>B){
			  while(1);
 
		  	//cout << "QAQ\n";
		  }
	  }
	  if (x>0){
	  	int dd=d[V2[x]]-d[V2[x-1]];
		if (dd<max(A[x-1], A[x]) || dd>B){
			while(1);
			//cout << "QAQ\n";
		}
	  }
  }
  for(int i = 0; i < K; ++i) {
	  if(V2[i] != P-1) {
		  while(1);
		  //cout<<"QAQ\n";
	  }
  }
  for(auto x: ans) {
	  cout<<(x+1)<<' ';
  }
  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