杂技
题目背景
小
L
L
L 在中考后在家人的催促下前去参观县城的马戏团。啊啊啊，刚刚发现相册里面这张照片找不到了。
题目描述
小 L L L 在刚开始的时候心不在焉，觉得真没意思，看到降龙伏虎、喷火表演真没意思，但当节目进行到人跳凳子的时候，小 L L L 此时来了兴致，津津有味的看着。
该节目就是：一个人起初站在最初的凳子上，一共要跳 n n n 个凳子（这些凳子都必须得跳到），而且他可以指挥助手给他放在特定的位置放 m m m 个凳子。此时小 L L L 想知道的是，他最少跳的最长的距离 l l l 是多少时，才能顺利的跳到最后一个凳子上？
但小 L L L 觉得还不够，他的想象力很丰富，因为每个人都有潜力，小 L L L 就假设有 k k k 次爆发力，那个人能跳最远 3 l 3l 3l 的距离。同时，小 L L L 把凳子的位置抽象成一个坐标，位置为 a i a_i ai。
但小 L L L 还不仅于此，他还想知道：因为每个人在跳跃的时候都得消耗体力，他定义 b i b_i bi 为第 i i i 个凳子的起跳的单位距离体力消耗量（也就是总的体力是： l × b i l\times b_i l×bi），此时，小 L L L 为了简化计算，把新增的凳子的体力消耗量不算入内。
小 L L L 的苦思冥想，因为他知道人脑没有电脑算的快，所以他要求你在 1 s 1s 1s 算出答案，因为他等不及了。快！！！
输入格式
输入第一行： n , m , k n,m,k n,m,k。
输入第二行： a 1 , a 2 , a 3 , . . . , a n + 1 a_1,a_2,a_3,...,a_{n+1} a1,a2,a3,...,an+1。
输入第二行： b 1 , b 2 , b 3 , . . . , b n + 1 b_1,b_2,b_3,...,b_{n+1} b1,b2,b3,...,bn+1。
题目不保证同一坐标与体力值一一对应，如果一对多的话，小 L L L 要求在输出的第二行按照排序后的坐标输出（也就是不去重）。
输出格式
输出第一行： l l l， 0 ≤ l ≤ 1 0 8 0\le l\le 10^8 0≤l≤108。
输出第二行：共有 n n n 个数，分别为在每个凳子起跳的体力消耗值 c i c_i ci。
输出第三行：从起点到终点体力总消耗量 C C C。
注意： 输出的第二行和第三行答案可能很大，我们要对答案对 1 , 000 , 000 , 007 1,000,000,007 1,000,000,007 取模。
样例 #1
样例输入 #1
5 3 1
0 1 3 8 16 21
1 1 1 1 2 4
样例输出 #1
3
3 3 3 3 6
18
提示说明
样例解释
当 l l l 为 3 3 3 时，表演者在上 x = 0 x=0 x=0 的凳子，叫助手在坐标为 10 , 13 , 19 10,13,19 10,13,19 的位置增加凳子，然后每次跳的距离为 1 , 2 , 2 , 5 , 3 , 3 , 3 , 2 1,2,2,5,3,3,3,2 1,2,2,5,3,3,3,2，在第四次起跳的时候使用一次爆发力。
接着， c 1 = 1 × 3 c_1=1\times 3 c1=1×3， c 2 = 1 × 3 c_2=1\times 3 c2=1×3 …… c 5 = 2 × 3 c_5=2\times 3 c5=2×3。
最后总的消耗量为： 3 + 3 + 3 + 3 + 6 = 18 3+3+3+3+6=18 3+3+3+3+6=18。
数据范围及规模
1 ≤ n , k ≤ 1 0 6 1\le n,k\le 10^6 1≤n,k≤106， 1 ≤ m ≤ 1 0 8 1\le m \le 10^8 1≤m≤108， 0 ≤ ∣ a i ∣ , b i ≤ 1 0 8 0 \le |a_i|,b_i \le10^8 0≤∣ai∣,bi≤108。
注意
题目不保证坐标的顺序是从小到大的。
// #include <iostream>
// #include <algorithm>
// #include <cstring>
// #include <stack>//栈
// #include <deque>//队列
// #include <queue>//堆/优先队列
// #include <map>//映射
// #include <unordered_map>//哈希表
// #include <vector>//容器，存数组的数，表数组的长度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
const ll p=1e9+7;
struct per
{
int x,y;
bool operator<(const per &t)
{
return x<t.x;
}
}a[N];
ll s[N];
ll n,m,k;
bool find(ll c)
{
ll cnt=0;//组数
for(ll i=1;i<=n;i++)
cnt+=max(0ll,(a[i].x-a[i-1].x+c-1)/c-1);
return cnt<=m+k;
}
int main()
{
cin>>n>>m>>k;
for(ll i=0;i<=n;i++)
{
cin>>a[i].x;
a[i].x+=N;
}
for(ll i=0;i<=n;i++)
cin>>a[i].y;
sort(a,a+n+1);
ll l=0,r=N;
while(l+1<r)
{
ll mid=(l+r)>>1;
if(find(mid)) r=mid;
else l=mid;
}
cout<<r<<endl;
for(ll i=0;i<n;i++)
{
cout<<(a[i].y*r)%p<<" ";
s[i+1]=s[i]+a[i].y;
}
puts("");
cout<<(s[n]*r)%p<<endl;
return 0;
}