Platformer

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
//package kilo.v2.t3;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 *
 * @author asjuvone
 */
public class KILOV2T3 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        IO io = new IO();
        int n = io.nextInt();
        int q = io.nextInt();
        int w = io.nextInt();
        int k = io.nextInt();
        int[] juomat = new int[n+1];
        int[] juomienArvot = new int[n+1];
        for (int i=1; i<=n; i++) {
            if (io.nextInt() == 0) juomat[i] = -1;
            else {
                juomat[i] = io.nextInt(); // x-koordinaatti juomalle tasolla i
                juomienArvot[i] = io.nextInt();
            }
        }
        
        TreeMap<Integer, TreeSet<Integer>> paikat = new TreeMap<>();
        TreeSet<Integer> lista = new TreeSet<>();
        lista.add(q);
        paikat.put(w, lista);
        for (int kerros=1; kerros<n; kerros++) {
            Iterator<Integer> it = paikat.descendingKeySet().iterator();
            int kuolemaRaja = (kerros-1) * k;
            int parasReittiJuomalle = kuolemaRaja+1;
            while (it.hasNext()) {
                int v = it.next();
                if (v < kuolemaRaja) break;
                
                Integer x = paikat.get(v).floor(juomat[kerros]);
                if (x != null) {
                    int vahennys = Math.abs(juomat[kerros] - x);
                    int lisays = juomienArvot[kerros];
                    int nykReittiJuomalle = v - vahennys + lisays;
                    if (nykReittiJuomalle > parasReittiJuomalle) {
                        parasReittiJuomalle = nykReittiJuomalle;
                        kuolemaRaja = parasReittiJuomalle;
                    }
                }
                x = paikat.get(v).ceiling(juomat[kerros]);
                if (x != null) {
                    int vahennys = Math.abs(juomat[kerros] - x);
                    int lisays = juomienArvot[kerros];
                    int nykReittiJuomalle = v - vahennys + lisays;
                    if (nykReittiJuomalle > parasReittiJuomalle) {
                        parasReittiJuomalle = nykReittiJuomalle;
                        kuolemaRaja = parasReittiJuomalle;
                    }
                }
            }
            TreeSet<Integer> uusLista = paikat.get(parasReittiJuomalle);
            if (uusLista == null) {
                uusLista = new TreeSet<Integer>();
                paikat.put(parasReittiJuomalle, uusLista);
            }
            uusLista.add(juomat[kerros]);
        }
        if (paikat.lastKey() > (k*(n-1))) System.out.println("10-4");
        else System.out.println("QAQ");
    }
    
}

class Paikka implements Comparable<Paikka> {
    List<Integer> xLista;
    int v;

    public Paikka(List<Integer> xLista, int v) {
        this.xLista = xLista;
        this.v = v;
    }


    @Override
    public int compareTo(Paikka o) {
        return o.v - this.v;
    }

    @Override
    public boolean equals(Object obj) {
        Paikka toinen = (Paikka) (obj);
        return toinen.v == this.v;
    }
    
    
    
    
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: TIME LIMIT EXCEEDED

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: ACCEPTED

Test 17

Verdict: TIME LIMIT EXCEEDED

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: ACCEPTED

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: TIME LIMIT EXCEEDED

Test 23

Verdict: TIME LIMIT EXCEEDED

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: TIME LIMIT EXCEEDED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: TIME LIMIT EXCEEDED

Test 29

Verdict: WRONG ANSWER

Test 30

Verdict: ACCEPTED

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: ACCEPTED

Test 50

Verdict: TIME LIMIT EXCEEDED

Test 51

Verdict: TIME LIMIT EXCEEDED