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

collectmushrooms4 Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

collectmushrooms4.html

Problem Description

Gug is collecting mushrooms again. This time he is collecting it in linear land, where there are N houses arranged in a row. Getting a permit to dig mushrooms in front of house i costs Ci dollars, but once it is bought, Gug can direct as many minions as he wants to dig mushrooms there. Gug has M minions. Minion i wants to pick mushrooms between houses Si and Ei, and will gain Hi dollars if it is allowed to do so. Help Gug decide a subset of minions to allow to pick mushrooms such that he gains the most amount of money.

Input

The first line of input will contain two integers, N and M.

The second line of input will contain N integers, representing the array C.

The next M lines of input will contain three integers each, Si, Ei and Hi.

Output

The output should contain one integer, the maximum net profit Gug can gain.

Limits

For all subtasks: 0 ≤ Si, Ei < N, 0 ≤ Hi, Ci ≤ 109.

Subtask 1 (10%): 1 ≤ N ≤ 500, 1 ≤ M ≤ 15.

Subtask 2 (12%): 1 ≤ N ≤ 2000, 1 ≤ M ≤ 20.

Subtask 3 (30%): 1 ≤ N ≤ 200, 1 ≤ M ≤ 200.

Subtask 4 (22%): 1 ≤ N ≤ 1000, 1 ≤ M ≤ 2000.

Subtask 5 (26%): 1 ≤ N ≤ 300000, 1 ≤ M ≤ 300000.

Subtask 6 (0%): Sample Testcases.

Sample Input 1

2 1
0 3
0 1 5

Sample Output 1

2

Sample Input 2

7 4
3 2 3 2 1 2 3
0 1 5
1 2 5
2 4 3
6 6 5

Sample Output 2

4

Tags

Dynamic Programming, Data Structure

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110221.5s256MBMinimum
212421.5s256MBMinimum
330221.5s256MBMinimum
422621.5s256MBMinimum
5261021.5s256MBMinimum
6021.5s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o collectmushrooms4 -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.