Call a Cab

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef long double ld;

int dp[101010];
ll dm[101010];
ll hr[101010];
ll d[101010];
ll h[101010];

ll inf=1e18;
int inf2=1e9;

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t,n;
	cin>>t>>n;
	for (int i=0;i<t;i++){
		cin>>dm[i]>>hr[i];
	}
	for (int i=1;i<n;i++){
		cin>>d[i]>>h[i];
		dp[i]=inf2;
	}
	dp[0]=0;
	for (int i=0;i<n-1;i++){
		for (int j=0;j<t;j++){
			ll td=0;
			ll ks=0;
			ll mik=inf;
			ll mak=-inf;
			for (int a=i+1;a<n;a++){
				td+=d[a];
				ks+=h[a];
				mik=min(mik, ks);
				mak=max(mak, ks);
				//cout<<mik<<" mima "<<mak<<endl;
				if (mak-mik<=hr[j]&&td>=dm[j]){
					//cout<<i<<" "<<a<<endl;
					dp[a]=min(dp[a], dp[i]+1);
				}
			}
		}
	}
	if (dp[n-1]<inf2){
		cout<<dp[n-1]<<endl;
	}
	else{
		cout<<"IMPOSSIBLE"<<endl;
	}
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: WRONG ANSWER

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: TIME LIMIT EXCEEDED