Platformer

#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <bitset>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

using namespace std;

#define ll long long
#define ld long double
#define ii pair<int,int>
#define si pair<string,int>
#define iii pair<int,ii>
#define vi vector<int>
#define vc vector<char>
#define vs vector<string>
#define msvs map<string,vs>
#define msi map<string,int>
#define mss map<string,int>
#define us unordered_set
#define um unordered_map
#define pq priority_queue
#define pb push_back
#define mp make_pair
#define forall(i,a,b) for (int i=a;i<b;i++)
#define foreach(v,c) for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a) a.begin(), a.end()
#define in(a,b) ( (b).find(a) != (b).end())
#define fill(a,v) memset(a, v, sizeof a)
#define sz(a) ((int)(a.size()))
#define N (1<<17)
#define M 1000000007
#define I 500000004

ll n,q,w,k;
pair<ll,ll> es[101010];

void go(ll energy, ll level, ll coord, ll sum)
{
	if (energy < 0) return;
	if (sum + energy < k*(n-level)) return;
	if (level == n) {
		cout << "10-4\n";
		exit(0);
	}
	ll x = es[level].first;
	ll e = es[level].second;
	if (x == 0) {
		go(energy-k,level+1,coord,sum);
	} else if (2*abs(coord-x) < e && energy >= abs(coord-x)) {
		go(energy+e-abs(coord-x)-k,level+1,x,sum-e);
	} else {
		go(energy-k,level+1,coord,sum-e);
		if (energy >= abs(coord-x)) go(energy+e-abs(coord-x)-k,level+1,x,sum-e);
	}
}

int main()
{
	cin.sync_with_stdio(false);
	cin >> n >> q >> w >> k;
	ll sum = 0;
	for (int i = 1; i <= n; i++) {
		int t; cin >> t;
		if (t) {
			ll x,e;
			cin >> x >> e;
			es[i] = make_pair(x,e);
			sum += e;
		} else {
			es[i] = make_pair(0,0);
		}
	}
	go(w,1,q,sum);
	cout << "QAQ\n";
	return 0;
}

Test 1

Verdict: TIME LIMIT EXCEEDED

Test 2

Verdict: TIME LIMIT EXCEEDED

Test 3

Verdict: TIME LIMIT EXCEEDED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: TIME LIMIT EXCEEDED

Test 10

Verdict: TIME LIMIT EXCEEDED

Test 11

Verdict: TIME LIMIT EXCEEDED

Test 12

Verdict: TIME LIMIT EXCEEDED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: TIME LIMIT EXCEEDED

Test 15

Verdict: TIME LIMIT EXCEEDED

Test 16

Verdict: TIME LIMIT EXCEEDED

Test 17

Verdict: TIME LIMIT EXCEEDED

Test 18

Verdict: TIME LIMIT EXCEEDED

Test 19

Verdict: TIME LIMIT EXCEEDED

Test 20

Verdict: TIME LIMIT EXCEEDED

Test 21

Verdict: TIME LIMIT EXCEEDED

Test 22

Verdict: TIME LIMIT EXCEEDED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: TIME LIMIT EXCEEDED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: TIME LIMIT EXCEEDED

Test 27

Verdict: TIME LIMIT EXCEEDED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: TIME LIMIT EXCEEDED

Test 30

Verdict: TIME LIMIT EXCEEDED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: TIME LIMIT EXCEEDED

Test 33

Verdict: TIME LIMIT EXCEEDED

Test 34

Verdict: TIME LIMIT EXCEEDED

Test 35

Verdict: TIME LIMIT EXCEEDED

Test 36

Verdict: TIME LIMIT EXCEEDED

Test 37

Verdict: TIME LIMIT EXCEEDED

Test 38

Verdict: TIME LIMIT EXCEEDED

Test 39

Verdict: TIME LIMIT EXCEEDED

Test 40

Verdict: TIME LIMIT EXCEEDED

Test 41

Verdict: TIME LIMIT EXCEEDED

Test 42

Verdict: TIME LIMIT EXCEEDED

Test 43

Verdict: TIME LIMIT EXCEEDED

Test 44

Verdict: TIME LIMIT EXCEEDED

Test 45

Verdict: TIME LIMIT EXCEEDED

Test 46

Verdict: TIME LIMIT EXCEEDED

Test 47

Verdict: TIME LIMIT EXCEEDED

Test 48

Verdict: TIME LIMIT EXCEEDED

Test 49

Verdict: TIME LIMIT EXCEEDED

Test 50

Verdict: TIME LIMIT EXCEEDED

Test 51

Verdict: TIME LIMIT EXCEEDED