Corsa ad ostacoli Terry

Aiuto
1

Salve a tutti!

Sto provando a risolvere https://territoriali.olinfo.it/task/ostacoli

Ecco il mio codice:

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;

import static java.lang.Math.abs;
import static java.lang.Math.max;

public class ostacoli {

    public static class Obstacle implements Comparable<Obstacle> {
        public int s;  // istante al quale appare
        public int p;  // valore punti
        public int x;  // distanza dalla partenza

        public Obstacle(int x, int p, int s) {
            this.s = s;
            this.p = p;
            this.x = x;
        }

        @Override
        public int compareTo(Obstacle o) {
            return Integer.compare(x, o.x);
        }
    }

    public static int N;
    public static int L;
    public static int D;
    public static Obstacle[] obstacles;

    public static long solve(int currObstacle , long currS) {
        if (currS >= D) {
            return 0;
        }

        long left = 0;  // go to the obstacle to the left
        long wait = 0;  // stand still
        long right = 0;  // go to the obstacle to the right

        if (obstacles[currObstacle].s == currS) {
            left = wait = right = obstacles[currObstacle].p;
        }

        if (currObstacle > 0) {
            long travelS = abs(obstacles[currObstacle].x - obstacles[currObstacle - 1].x);
            left += solve(currObstacle - 1, currS + travelS);
        }

        if (currS < obstacles[currObstacle].s) {
            wait += solve(currObstacle, currS + 1);
        }

        if (currObstacle < N - 1) {
            long travelS = abs(obstacles[currObstacle].x - obstacles[currObstacle + 1].x);
            right += solve(currObstacle + 1, currS + travelS);
        }

        return max(wait, max(left, right));
    }


    public static void main(String[] args) throws FileNotFoundException {
        InputStream fin;
        fin = System.in;
        fin = new FileInputStream("C:\\Users\\Alex\\Downloads\\ostacoli_input_1.txt");
        Scanner in = new Scanner(fin);

        OutputStream fout;
        fout = System.out;
        fout = new FileOutputStream("C:\\Users\\Alex\\Downloads\\ostacoli_output_1.txt");
        PrintStream prnt = new PrintStream(fout);

        int T = in.nextInt();

        for (int t = 1; t <= T; t++) {
            prnt.print("Case #" + t + ": ");

            N = in.nextInt();
            L = in.nextInt();
            D = in.nextInt();

            obstacles = new Obstacle[N];
            for (int i = 0; i < N; i++) {
                obstacles[i] = new Obstacle(in.nextInt(), in.nextInt(), in.nextInt());
            }

            Arrays.sort(obstacles);

            prnt.println(solve(0, obstacles[0].x));
        }
    }
}

Ho pensato di risolverlo tramite backtracking.

Non penso si possa applicare dp in quanto L e D arrivano fino a 10^9 e quindi sforerebbero la memoria.

In ogni caso il programma và in stack overflow error anche con input piccoli.

L’unica soluzione che mi viene in mente è fare pruning sulle chiamate ricorsive, ma pur avendo fatto qualche test non risolvo il problema.

Qualche hint?