LCC '18 Contest 4 S3 - Flight Plan

View as PDF

Submit solution

Points: 7
Time limit: 2.0s
Memory limit: 64M

Problem types

Howard has recently started a new full-time job which gives him \(K\) vacation days to use during the year. He is looking to spend all of his vacation days on a single trip to Hanoi, however he is having a hard time finding a pair of flights that are exactly \(K\) days apart.

Given the \(N\) flights to and from Hanoi this year, find the minimum cost of two flights \(A\) and \(B\) such that:

  • \(A\) is a flight to Hanoi.
  • \(B\) is a flight from Hanoi.
  • \(A\) and \(B\) are exactly \(K\) days apart.

Input Specification

The first line of input contains two integers \(N, K\) \((1 \le N \le 100\ 000, 1 \le K \le 10^9)\), the number of flights and the number of vacation days that Howard has.

The next \(N\) lines each contain three terms \(D, T, C\) describing a flight, where:

  • \(D\) \((1 \le D \le 10^9)\) is the day the flight departs.
  • \(T\) is either T or F, representing whether the flight is to or from Hanoi, respectively.
  • \(C\) \((1 \le C \le 10^9)\) is the cost of the flight.

Output Specification

Output the minimum cost of a pair of flights satisfying the conditions in the problem description, or -1 if no such pair exists.

Sample Input 1

2 3
1 F 1000
4 T 1000

Sample Output 1


Sample Input 2

3 5
1 T 1000
3 T 100
6 F 1000

Sample Output 2



There are no comments at the moment.