Train

#include <bits/stdc++.h>

using namespace std;

typedef bitset<20> bs;
typedef int64_t ll;
typedef pair<ll,ll> PLL;
typedef pair<int, pair<int,int>> PQ;

// [a][b][t] start a end b start at time t
  int vals[100][100][501];

int main() {

  cout << std::setprecision(15);

  int n, t, x;
  cin >> n >> t >> x;

  x--;
  
  vector<int> v (n);
  vector<int> k (n);
  for (int i=0; i<n; i++) {
    cin >> v[i] >> k[i];
    k[i];
  }


  // [a][b][t] been to a, now at b, time now t

  for (int a=0; a<n; a++) {
    vals[a][a][t] = v[a];
  }
  
  for (int tt=t; tt>=0; tt--) {
    for (int a=0; a<n; a++) {
      for (int b=0; b<n; b++) {
        //Been to a, now at b, time now tt;
        int samedir = (b>a) ? 1 : -1;
        if (vals[a][b][tt] == 0) { continue; }

        for (int dir : {-1, 1}) {
          int val = vals[a][b][tt];
          int tnew = tt;

          int cstart = b+dir;
          int oldext = a;
          if (dir!=samedir) {
            cstart = a+dir;
            tnew -= abs(a-b);
            oldext = b;
          }
          
          for (int c = cstart; c>=0 && c<n; c+=dir ) {
            tnew --;
            if (tnew < abs(c-x)) { break; }
            
            if (tnew >= k[c] ) { val += v[c]; }
            //            cout << "From " << a << " " << b << " " << tt << " to " << c << " val " << vals[a][b][tt] << " to " << val << endl;
            vals[oldext][c][tnew] = max(vals[oldext][c][tnew], val);
          }
        }
      }
    }
  }

  for (int tt=t; tt>=0; tt--) {
    for (int a=0; a<n; a++) {
      for (int b=0; b<n; b++) {
        //        cout << a << " " << b << " " << tt << " : " << vals[a][b][tt] << endl;
      }
    }
  }
  
  int res = 0;
  for (int a=0; a<n; a++) {
    for (int b=0; b<n; b++) {
      for (int tt=abs(b-x); tt<=t; tt++) {
        res = max(res, vals[a][b][tt]);
      }
    }
  }

  cout << res << endl;

  
  

}

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

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED