#2423. 购买饲料

购买饲料

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

约翰开车来到镇上,他要带K\red{K}吨饲料回家。运送饲料是需要花钱的,如果他的车上有X\red{X}吨饲料,每公里就要花费X2\red{X^2}元,开车D\red{D}公里就需要D×X2\red{D\times X^2}元。约翰可以从N\red{N}家商店购买饲料,所有商店都在一个坐标轴上,第i\red{i}家店的位置是Xi\red{X_i,}饲料的售价为每吨Ci\red{C_i}元,库存为Fi\red{F_i}

约翰从坐标X=O\red{X=O}开始沿坐标轴正方向前进,他家在坐标X=E\red{X=E}上。为了带K\red{K}吨饲料回家,

约翰最少的花费是多少呢?假设所有商店的库存之和不会少于K\red{K}

举个例子,假设有三家商店,情况如下所示:

坐标 X=1    X=3    X=4    E=5\red{X=1 ~ ~~~X=3 ~ ~~~ X=4 ~~ ~~E=5}

库存      1             1             1\red{ ~~~~~1 ~~~ ~~~~~ ~~~~~ 1 ~~~ ~~~~~ ~~~~~ 1}

售价      1             2             2\red{ ~~~~~1 ~~~ ~~~ ~~~~~~~ 2 ~~~ ~~~~~ ~~~~~ 2}

如果K=2\red{K=2,}约翰的最优选择是在离家较近的两家商店购买饲料,则花在路上的钱是1+4=5\red{1+4=5,}花在商店的钱是2+2=4\red{2+2=4,}共需要9\red{9}元。

输入格式

1\red{1}行:三个整数K,E,N\red{K,E,N }

2..N+1\red{2..N+1}行:第i+1\red{i+1}行的三个整数代表,Xi,Fi,Ci.\red{X_i,F_i,C_i.}

输出格式

一个整数,代表最小花费

样例

输入样例

2 5 3
3 1 2
4 1 2
1 1 1

输出样例

9

数据结构

未参加
状态
已结束
规则
IOI
题目
14
开始于
2023-1-7 14:00
结束于
2023-1-8 14:00
持续时间
24 小时
主持人
参赛人数
18