oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

moonwalk Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

statement.html

Problem Description

Desmond the Moonbear is stuck on the moon. He does not know how he got there. Help him get home

The moon is linear. Desmond starts from position 0 and wants to go home to position n [in metres]

It takes him 1 second to move 1 metre on the moon [The gravity is very low]

There are c magical craters on the moon. Each crater starts from position si and ends at position ei and takes ti time to transverse [Warning: ti is not necessarily smaller than ei-si+1]

Desmond is afraid of the dark, so he is willing to go through at most m craters

No 2 craters will intersect due to spacing considerations [for 2 distinct integers i and j, if si<sj, ei<sj]

No crater will end after Desmond's house [i.e. for all i, si<n]

Input

The first line of the input consists of 3 integers, n, m and c

Next c lines of input consists of 3 integers per line, si, ei and ti

No 2 craters will intersect [for 2 distinct integers i and j, if si<sj, ei<sj]

All craters will be given in sorted starting order

Output

A single integer t representing the minimum amount of time Desmond will take to get home.

Subtasks

Subtask 1 (15%) n<=1000,c<=10

Subtask 2 (30%) n<=1000000,c<=1000

Subtask 3 (55%) n<=1000000000,c<=1000000

Subtask 4 (0%) will be the sample testcases

Sample Testcase 1

Input

6 1 2
1 3 4
3 5 1
Output
5

Explanation

Desmond walks from position 0 to position 3, taking 3 time.

Desmond takes tunnel 2, taking 1 time and ending up at position 5.

Desmond walks from position 5 to position 6 [home], taking 1 time.

Therefore, Desmond took 5 time

Tags

Greedy

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
115102s32MBMinimum
230102s32MBMinimum
355102s32MBMinimum
4012s32MBMinimum

Judge Compile Command

g++-8 ans.cpp -o moonwalk -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.