#P1348. [Baltic2006]City

    ID: 360 传统题 1000ms 512MiB 尝试: 87 已通过: 31 难度: 6 上传者: 标签>CF2000提高二分第 k 小等差数列求和倍增寻找边界向下取整与向上取整

[Baltic2006]City

题目描述

一个空间站占据无限方格平面中坐标为 (0,0)(0,0) 的地块,其他整数坐标 (x,y)≠(0,0)(x,y)\ne(0,0) 表示可建住宅的地块,这个空间站需要雇佣 nn(1≤n≤10121\leq n\leq 10^{12})个员工。为了解决住宿问题,政府需要建设一个城市,城市包括一些最高不超过 kk(1≤k≤2×1041\leq k\leq 2\times 10^4)层的单元房。一个 kk 层的单元房占地为 1×11\times 1 的单元格,可以住 kk 人,一个单元房在 ii 层的情况下增加一层需要花费 ci+1c_{i+1}(1≤ci≤2×1091\leq c_i\leq 2\times 10^9)元,满足 c1<c2<⋯<ckc_1 < c_2 < \cdots < c_k。城市中还需要建设交通网络,对于每个员工 ii,交通建设花费为 T×diT\times d_i(1≤T≤5×1051\leq T\leq 5\times 10^5),其中 did_i 表示该员工所住单元房与空间站的距离(注:(x, y)(x,\ y) 与空间站的距离为 ∣x∣+∣y∣−1|x|+|y|-1)。

请输出安排 nn 人住宿的最小花费。

输入格式

第一行包含三个整数 N,T,KN,T,K。接下来 KK 行,第 ii 行给出 cic_i。

输出格式

输出最少花费。保证答案不超过 8×10188\times10^{18}。

17 5 4
100
107
114
121
1778