题目详情题解（0）讨论（0）提交记录（0）

AT_abc404_g.[ABC404G] Specified Range Sums

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给你一个整数 NN 和 MM 个整数三元组 (Li,Ri,Si)(L_i,R_i,S_i)。

判断是否存在一个长度为 NN 的正整数数列 AA，满足对于所有的三元组限制 (Li,Ri,Si)(L_i,R_i,S_i)，满足 ∑j=LiRiAj=Si\sum\limits_{j=L_i}^{R_i}A_j=S_i。如果存在，找出合法的 AA 的最小元素和。

输入格式

第一行两个整数 N,M(1≤N,M≤4000)N,M(1\le N,M\le 4000)。
接下来 MM 行，每行三个整数 Li,Ri,Si(1≤Li≤Ri≤N,1≤Si≤109)L_i,R_i,S_i(1\le L_i\le R_i\le N,1\le S_i\le 10^9)。

输出格式

如果不存在符合条件的 AA，输出一个整数 −1-1。
否则，输出一个整数，表示合法的 AA 的最小元素和。

输入输出样例

  • 输入#1

    5 3
1 2 4
2 3 5
5 5 5

    输出#1

    12

  • 输入#2

    1 2
1 1 1
1 1 2

    输出#2

    -1

  • 输入#3

    9 6
8 9 8
3 6 18
2 4 19
5 6 8
3 5 14
1 3 26

    输出#3

    44

说明/提示

样例 1 解释

A=(1,3,2,1,5)A=(1,3,2,1,5) 是一种符合条件的情况。
此情况下 AA 的和是 1212，可以证明这是可能的最小值。

样例 2 解释

此时无解。

By chenxi2009

输入解题思路，AI测评打分。不知道怎么写?

首页