普及T1 数字反转
模拟1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
using namespace std;
char num[15];
int main(){
scanf("%s",num);
int f=(num[0]=='-'),len=strlen(num),cur=0;
reverse(num,num+len);
while(num[cur]=='0')cur++;
if(f)putchar('-');
if(!num[cur]||num[cur]=='-')printf("0\n");
else{
while(isdigit(num[cur]))putchar(num[cur]),cur++;
}
return 0;
}
普及T2 统计单词数
本题不需要使用字符串匹配的高级算法，模拟即可。
注意单词必须完全匹配，即匹配时两个单词长度要一样。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
using namespace std;
char w[20],s[1000005];
int ans1=-1,ans2=0,l1,l2;
bool judge(int t){
for(int i=0;i<l1;i++)
if(w[i]!=s[t+i])return 0;
if(t+l1==l2||s[t+l1]==' ')return 1;
return 0;
}
int main(){
scanf("%s",w);
while(getchar()!='\n');
fgets(s,1000003,stdin);
l1=strlen(w),l2=strlen(s);
for(int i=0;i<l1;i++)if(isupper(w[i]))w[i]+='a'-'A';
for(int i=0;i<l2;i++)if(isupper(s[i]))s[i]+='a'-'A';
for(int i=0;i<l2;i++)
if(s[i]!=' '&&(!i||s[i-1]==' ')&&i+l1-1<l2)
if(judge(i)){
if(ans1<0)ans1=i;
ans2++;
}
if(ans1<0)printf("%d\n",ans1);
else printf("%d %d\n",ans2,ans1);
return 0;
}
普及T3 瑞士轮
模拟+归并。
直接模拟的话是$O(nqlogn)$的时间复杂度，会超时。
发现每次比完赛之后赢的人和输的人各自的相对排名不变，所以将胜者和败者归并起来，时间复杂度为$O(nq)$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
using namespace std;
typedef pair<int,int> P;
P p[200005],pp[200005];
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int n,r,q,w[200005],q1[200005],q2[200005],r1,r2;
//q1胜者 q2败者
void Merge(){
int tot=0,lb=1,rb=1;
while(lb<=r1&&rb<=r2){
int L=q1[lb],R=q2[rb];
if(p[L]<p[R])pp[++tot]=p[L],lb++;
else pp[++tot]=p[R],rb++;
}
while(lb<=r1)pp[++tot]=p[q1[lb]],lb++;
while(rb<=r2)pp[++tot]=p[q2[rb]],rb++;
memcpy(p+1,pp+1,sizeof(P)*n);
}
void init(){
n=read()<<1,r=read(),q=read();
for(int i=1;i<=n;i++)
p[i].first=-read(),p[i].second=i;
for(int i=1;i<=n;i++)w[i]=read();
sort(p+1,p+n+1);
}
void solve(){
while(r--){
r1=r2=0;
for(int i=1;i<=n;i+=2){
q1[++r1]=i,q2[++r2]=i+1;
if(w[p[i].second]<w[p[i+1].second])
swap(q1[r1],q2[r2]),p[i+1].first--;
else p[i].first--;
}
Merge();
}
printf("%d\n",p[q].second);
}
int main(){
init();
solve();
return 0;
}
普及T4 表达式的值
$DP$。
实际上那两个运算就是与和或，所以直接用栈来模拟一下运算过程即可。
按运算数来$DP$，记录一下当前编号为$id$的运算数取$0$和$1$时的方案数，这样做法就比较显然了，在模拟的时候计数即可。时间复杂度为$O(n)$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
using namespace std;
int s1[100005][2]={0},s2[100005]={0},t1=0,t2=0,pro[300],lim,M=10007;
char _exp[100005];
void opr(){
int a1,a2,b1,b2,o;
a1=s1[--t1][0],a2=s1[t1][1],
b1=s1[--t1][0],b2=s1[t1][1],
o=s2[--t2];
if(o=='+')
s1[t1][0]=(a1*b1)%M,
s1[t1++][1]=(a1*b2+a2*b1+a2*b2)%M;
if(o=='*'){
s1[t1][1]=(a2*b2)%M,
s1[t1++][0]=(a1*b1+a1*b2+a2*b1)%M;
}
}
void calc(){
int i,j;
for(i=0;i<lim;i++){
if(_exp[i]=='(')
s2[t2++]='(';
else if(_exp[i]==')'){
while(s2[t2-1]!='(')
opr();
t2--;
}else{
if(_exp[i-1]!=')')
s1[t1][0]=1,
s1[t1++][1]=1;
while(t2&&s2[t2-1]!='('&&
pro[s2[t2-1]]>=pro[_exp[i]])
opr();
s2[t2++]=_exp[i];
if(_exp[i+1]==')')
s1[t1][0]=1,
s1[t1++][1]=1;
}
}
}
void init(){
pro['+']=1,pro['*']=2;
scanf("%d%s",&lim,&_exp[1]);
lim++;
_exp[0]='(';
_exp[lim++]=')';
}
void solve(){
calc();
printf("%d\n",s1[0][0]);
}
int main(){
init();
solve();
return 0;
}
提高D1T1 铺地毯
模拟即可。注意判断矩形和无解条件。1
2
3
4
5
6
7
8
9
10
11
12
13
14
int x[10002],y[10002],l[10002],w[10002],n,dx,dy;
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d%d%d",&x[i],&y[i],&l[i],&w[i]);
scanf("%d%d",&dx,&dy);
int at=-1;
for(int i=0;i<n;i++)
if((dx<=x[i]+l[i]&&dx>=x[i])&&(dy<=y[i]+w[i]&&dy>=y[i]))
at=i+1;
printf("%d\n",at);
return 0;
}
提高D1T2 选择客栈（待考察）
直接枚举是$O(n^2)$的，不够优秀。
考虑这么一种做法：我们分颜色考虑，对于一种颜色$col$，用某个数据结构按距离从大到小存一下客栈的编号（其实从小到大还是从大到小不重要），然后按顺序枚举每一个客栈，统计一下它的贡献。（也就是有几种方案，他被住下了）
贡献怎么算呢？我们画个图
$cur$表示我们找到的离当前枚举到的客栈最近的合法（指最低消费$\le p$）客栈的编号，那么由乘法原理，这个时候$cur$左边的颜色为$col$的客栈数乘上右边颜色为$col$的客栈数就是可行的贡献。
诶，刚才不是说算每一个客栈的贡献么？
对的。这里由于$cur$右边的$col$颜色客栈之间没有合法客栈，所以把右边的一起算。
这里还有一个问题：如果$cur$的颜色是$col$怎么办？如果$cur$右边的客栈全被统计过了，就把他划分到右边，否则划分到左边，这样可以保证正确性。
计算完后继续看下一个客栈，这里有一个优化：如果客栈编号大于$cur$就直接跳过，因为他的贡献算过了。
综上，使用以上算法的时间复杂度为$O(nk)$。由于数据的原因，实际时间复杂度远小于该值。
本题还存在一个时间复杂度仅为$O(n)$的算法，可根据以上算法优化而来，各位不妨自行思考。
提示：如果我们边读入数据，边动态更新$cur$会怎么样呢？1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int n,k,p,col[200005],cost[200005];
int at[55],id[200005],nex[200005],cnt=0,tot[55];
void init(){
n=read(),k=read(),p=read();
for(int i=1;i<=n;i++){
col[i]=read(),cost[i]=read();
id[++cnt]=i,nex[cnt]=at[col[i]],at[col[i]]=cnt,tot[col[i]]++;
}
//链式前向星
}
void solve(){
int ans=0;
for(int i=0;i<k;i++){
if(!at[i])continue ;
int lf=tot[i],cur=id[at[i]]+1;
//lf 左端 rt 右端
for(int j=at[i];j;j=nex[j]){
if(id[j]>cur)continue;//优化，该客栈被统计过就跳过
int rt=0;//一开始cur右边没被统计过的客栈数是0
for(cur=id[j];cur&&cost[cur]>p;cur--)//更新cur
if(col[cur]==i)rt++,lf--;//遇到一个客栈在cur右边
if(!cur)break;//找不到这样的合法客栈
if(col[cur]==i&&!rt)rt=1,lf--;//对应右边无客栈被统计的情况
ans+=rt*lf;//计算贡献
}
}
printf("%d\n",ans);
}
int main(){
init();
solve();
return 0;
}
提高D1T3 Mayan游戏
本题模拟的成分远大于搜索。
由于步数已经确定，所以只要采用最简单的$DFS$即可求出结果。
当然，我们需要一些必要的剪枝和优化：
- 列表内容最优化剪枝：按照$x,y$的顺序遍历方块，保证第一个找到的可行方案一定是最优方案。
- 最优化剪枝：只有当左边是空的时候才左移，否则等价于左边的右移。
- 最优化剪枝：不移动同色方块。
- 可行性剪枝：有某种方块个数$\le 2$直接退出，因为不可能消除。
- 程序上的优化：用$2$个队列处理事件，一个处理掉落，一个处理消除。
这样就可以跑的非常快了。理论上还可以加一个估价的优化，就是通过同色方块的连接情况判断至少还要走几步，但实际上以上的优化已经足够了。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
//交换2个方块后要处理影响
//1.掉落 2.消除
//可行性剪枝：同颜色<=2个退出
//设置一个掉落队列和一个事件队列
//事件队列检查是否有可以消除的方块，有的话就把最上面一层得上一个加入掉落队列
//在掉落队列里检查上方是否有方块，有的话将上方的方块下降后全部加入事件队列
//两者需要交替进行。
int pz[10][5][7];
int n,ans[10][3],movement[10][3],cnt[11],flag=0;
int dque[10005][2],dr,df;//掉落队列
int eque[10005][2],er,ef;//事件队列
int visx[10],visy[10],vis[5][7];
void solve_clear(int cur){
int dx,dy,col,len;
for(int i=0;i<5;i++)visx[i]=0;
for(int i=0;i<7;i++)visy[i]=0;
memset(vis,0,sizeof(vis));
while(er>ef){
dx=eque[ef][0],dy=eque[ef++][1];
if(!visx[dx]){//同一个x
visx[dx]=1;
col=pz[cur][dx][0],len=1;
for(int i=1;i<7;i++){
if(pz[cur][dx][i]==col)
len++;
else{
if(len>=3&&col){
for(int j=i-1;i-j<=len;j--)vis[dx][j]=1;
}
col=pz[cur][dx][i],len=1;
}
}
if(len>=3&&col){
for(int j=6;7-j<=len;j--)vis[dx][j]=1;
}
}
if(!visy[dy]){
visy[dy]=1;
col=pz[cur][0][dy],len=1;
for(int i=1;i<5;i++){
if(pz[cur][i][dy]==col)
len++;
else{
if(len>=3&&col){
for(int j=i-1;i-j<=len;j--)vis[j][dy]=1;
}
col=pz[cur][i][dy],len=1;
}
}
if(len>=3&&col){
for(int j=4;5-j<=len;j--)vis[j][dy]=1;
}
}
}
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
if(vis[i][j]){
pz[cur][i][j]=0;
if(j!=6)
dque[dr][0]=i,dque[dr++][1]=j+1;
}
}
void solve_drop(int cur){
int dx,dy,des;
while(dr>df){
dx=dque[df][0],dy=dque[df++][1];
for(des=dy-1;des>=0&&!pz[cur][dx][des];des--);
des++;
for(int i=dy;i<7;i++)
if(pz[cur][dx][i])
pz[cur][dx][des++]=pz[cur][dx][i],
eque[er][0]=dx,eque[er++][1]=des-1;
for(int i=des;i<7;i++)
pz[cur][dx][i]=0;
}
}
void dfs(int cur){
if(flag)return ;
if(cur==n){
for(int i=0;i<5;i++)
if(pz[cur][i][0])return ;
memcpy(ans,movement,sizeof(ans));
flag=1;
return ;
}
for(int i=1;i<=10;i++)cnt[i]=0;
for(int i=0;i<5;i++)
for(int j=0;j<7;j++)
cnt[pz[cur][i][j]]++;
for(int i=1;i<=10;i++)
if(cnt[i]&&cnt[i]<3)return ;
for(int i=0;i<5;i++){
for(int j=0;j<7;j++){
if(!pz[cur][i][j])continue;
if(i!=4&&pz[cur][i+1][j]!=pz[cur][i][j]){
//向右移动
memcpy(pz[cur+1],pz[cur],sizeof(pz[0]));
swap(pz[cur+1][i+1][j],pz[cur+1][i][j]);
dr=df=0,ef=er=0;
dque[dr][0]=i,dque[dr++][1]=j,
dque[dr][0]=i+1,dque[dr++][1]=j;
while(dr>df)
solve_drop(cur+1),solve_clear(cur+1);
movement[cur][0]=i,movement[cur][1]=j,movement[cur][2]=1;
dfs(cur+1);
}
if(i&&!pz[cur][i-1][j]&&pz[cur][i-1][j]!=pz[cur][i][j]){//向左边
memcpy(pz[cur+1],pz[cur],sizeof(pz[0]));
swap(pz[cur+1][i-1][j],pz[cur+1][i][j]);
dr=df=0,ef=er=0;
dque[dr][0]=i,dque[dr++][1]=j,
dque[dr][0]=i-1,dque[dr++][1]=j;
while(dr>df){
solve_drop(cur+1),solve_clear(cur+1);
}
movement[cur][0]=i,movement[cur][1]=j,movement[cur][2]=-1;
dfs(cur+1);
}
}
}
}
void init(){
n=read();
int t;
for(int i=0;i<5;i++)
for(int j=0;j<8;j++){
t=read();
if(!t)break;
pz[0][i][j]=t;
}
}
void solve(){
dfs(0);
if(!flag)printf("-1\n");
else {
for(int i=0;i<n;i++)
printf("%d %d %d\n",ans[i][0],ans[i][1],ans[i][2]);
}
}
int main(){
freopen("a.in","r",stdin);
init();
solve();
return 0;
}
提高D2T1 计算系数
套用二项式定理和组合数取模即可。
$x^ny^m$的系数是$C_n^k \times a^n\times b^m$。
时间复杂度：$O(k^2)$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
int dp[1005]={0},a,b,k,m,n,ans;
int Pow(int a,int b){
int res=1;
while(b){
if(b&1)res=(res*a)%M;
a=(a*a)%M,b>>=1;
}return res;
}
int main(){
scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
a%=M,b%=M,dp[0]=1;
for(int i=1;i<=k;i++)
for(int j=i;j>=1;j--)
dp[j]+=dp[j-1],dp[j]%=M;
//计算组合数
ans=(dp[n]*Pow(a,n))%M,
ans=(ans*Pow(b,m))%M;
printf("%d\n",ans);
return 0;
}
提高D2T2 聪明的质监员
较为明显的二分。
二分一个$x$，然后扫一遍表，看看哪些$w$大于等于$x$，然后用前缀和存一下符合条件的$w$前缀和与$w$的数量前缀和，最后$m$个区间算一遍加起来即可。
时间复杂度：$O((n+m)logn)$1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
using namespace std;
typedef long long ll;
ll S,tot,v[200005],ans,sum[200005],cnt[200005];
int w[200005],n,m,ev[200005][2];
void solve(int r){
int i;
sum[0]=cnt[0]=0;
for(i=1;i<=n;i++){
sum[i]=sum[i-1],
cnt[i]=cnt[i-1];
if(w[i-1]>=r)sum[i]+=v[i-1],cnt[i]++;
}
for(i=0;i<m;i++)
tot+=(cnt[ev[i][1]]-cnt[ev[i][0]-1])*
(sum[ev[i][1]]-sum[ev[i][0]-1]);
}
int main(){
scanf("%d%d%lld",&n,&m,&S);
int i,j,lb=0,rb=1000000,md;
ans=S;
for(i=0;i<n;i++)
scanf("%d%lld",&w[i],&v[i]);
for(i=0;i<m;i++)
scanf("%d%d",&ev[i][0],&ev[i][1]);
while(rb-lb){
md=(rb+lb)/2,tot=0;
solve(md);
if(tot==S){ans=0;break;}
else if(tot>S)ans=min(ans,tot-S),lb=md+1;
else ans=min(ans,S-tot),rb=md;
}
printf("%lld\n",ans);
return 0;
}
提高D2T3 观光公交（待考察）
题解
题目的意思就是选择若干条路，修改他们的长度，使得总的旅行时间最少。
具体的做法就是贪心，找省时间最多的路段用。
我们把道路分块，为什么要这么做呢？我们把本题第一个数据画成图。1
2
3
4
5
6
710 5 0
5 7 2 4 8 2 8 3 1
10 3 4
1 1 3
33 6 9
14 4 8
1 1 4
上面的竖线表示到站的人的到站时间，点表示时间点。虚线部分是指车子到站之后还要等待虚线的时间才能等到人全部上齐。虚线左端是到站时间点，右端是发车时间点。
设一个站i中，来的最晚的人到达时间是$latest[i]$。然后，我们手算后可以发现一些性质：
性质1.如果车子到达i站的时间是$curt$，并且$curt\le latest[i]$，那么$i$前面和$i$后面，两个路段相互独立。
什么意思呢？我们可以感性地这么想：让一段路的长度减少，就相当于把这段路以及其后面的到站时间点往前拉。但是第i站的点永远不会动，因为他的到站时间点和发车时间点是用虚线连接着的，发车时间一定不变。所以对i前面的路修改，$i$后面的就不会受影响；同理对$i$后面的路修改，$i$前面的路也不会受影响。
我们称呼到达这样的站的路为隔离路。上图中，$5\rightarrow 6$就是隔离路。
根据这个性质，我们可以很方便的把路分块，分割成几个相互不影响的路块以及分隔他们的隔离路。
分完了块就可以计算优化一条路能节省的时间了。下面我们对一个路块进行探究：
设一个块中开头的站编号为$belong$，末尾的站是$tail$。显然，由上文，$tail\rightarrow tail+1$的路是隔离路。
性质2.一个块中，如果优化$i\rightarrow i+1$站的路，使其长度$-1$，可以节省的时间是在$i+1,i+2,…tail,tail+1$这些站下车的人数的总和。
这个性质很容易证明，由于这些人都已经上了车，所以优化这段路就相当于把后面站的到站时间点都$-1$，每一个人的到达时间就$-1$，所以省下的时间是人数的和，证毕。
根据这个性质，我们可以用后缀和计算出省下的时间，找到在块中最优的那段路。不在块中的隔离路也能优化，优化一次节省的时间是在隔离路通向的下一站下车的人数。
接下来的问题是一段路最多可以优化多少次。根据上图可以发现，一段路被优化一定次数，前面的某一段路就会变成隔离路。比如优化$1\rightarrow 2$的路后，$3\rightarrow 4$就变成了隔离路。所以在分块时还要对每一段路统计一个$mingap$，表示一段路最多优化几次就会导致后面的某段路变为隔离路。优化$mingap$次数之后，原来的块就失效了，需要对当前操作块进行重构。
如果一段路的长度变成了$0$，或者$mingap$为$0$，就称这一段路是无效路，在寻找最大值时忽略。
之后重复以上步骤即可。
分析一下时间复杂度：
每一轮我们找出一段可以修改的路，修改完成后，至少会使得一段路变为隔离路，或者使得一条隔离路变为无效路。所以每一条路最多被修改$2$次。一共有$O(n)$条路，所以最多做$O(n)$次，所有的路就被修改完了。
每一轮我们需要$O(n)$的时间找到省时间最多的路段，并且至多用$O(n)$的时间更新块的情况，结合上面可知，最多做$O(n)$轮，所以该算法的理论时间复杂度为$O(n^2)$。
贪心的正确性比较显然，在此不证明。
存在$O(nk)$的编程复杂度更低，但是可能会超时的做法。很可惜，本题数据太水，根本卡不掉。
事实上，本题存在时间运行上比本题解程序实现更优的程序实现。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
using namespace std;
typedef long long ll;
int read(){
int f=1,x=0;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
int n,m,K,dis[1005],latest[1005],dec[1005],cost[1005],cnt[1005],cnt2[1005];
int belong[1005],mingap[1005],tail[1005],ans=0;
void build_block(int l,int r){
int bid=l,curt=latest[l];
for(int i=l+1;i<=r;i++){
curt+=dis[i-1];
if(curt>latest[i])belong[i-1]=bid;
else{
belong[i-1]=-1,mingap[i-1]=INF;
int tmp=curt-dis[i-1];
for(int j=i-2;j>=bid;j--)
mingap[j]=min(min(tmp-latest[j+1],dis[j]),mingap[j+1]),
tmp-=dis[j];
curt=latest[i],tail[bid]=i-1,bid=i;
}
}
if(bid!=r){
int bef=INF;
for(int j=r-1;j>=bid;j--)
mingap[j]=min(bef,min(dis[j],curt-latest[j+1])),
bef=min(bef,mingap[j]),curt-=dis[j];
tail[bid]=r;
}
}
void init(){
n=read(),m=read(),K=read();
for(int i=1;i<n;i++)dis[i]=read();
for(int i=1;i<=m;i++){
int Ti=read(),Ai=read(),Bi=read();
latest[Ai]=max(latest[Ai],Ti);
cost[Ai]+=Ti;
dec[Ai]++,dec[Bi]--,cnt[Ai]++,cnt2[Bi]++;
}
for(int i=2;i<=n+1;i++)dec[i]+=dec[i-1];
int curt=latest[1];
ans+=cnt[1]*latest[1]-cost[1];
for(int i=1;i<n;i++){
if(latest[i+1]>curt+dis[i]){
ans+=cnt2[i+1]*dis[i]+(dec[i]-cnt2[i+1])*(latest[i+1]-curt);
ans+=cnt[i+1]*latest[i+1]-cost[i+1];
curt=latest[i+1];
}else{
ans+=dec[i]*dis[i],curt+=dis[i];
ans+=cnt[i+1]*curt-cost[i+1];
}
}
//每一段路上坐车人数
}
void solve(){
build_block(1,n);
for(;K;){
int maxi=0,maxid=-1,curb=0,bid,sum;
for(int i=1;i<n;i++){
bid=belong[i];
if(bid<0){
if(dis[i]&&cnt2[i+1]>maxi)maxi=cnt2[i+1],maxid=i;
}else{
if(curb!=bid){
curb=bid,sum=0;
for(int j=tail[bid]+1;j>=i+1;j--)sum+=cnt2[j];
}
if(mingap[i]&&sum>maxi)maxi=sum,maxid=i;
sum-=cnt2[i+1];
}
}
if(maxid<0)break;
bid=belong[maxid];
if(bid<0){
if(K>dis[maxid])
ans-=maxi*dis[maxid],K-=dis[maxid],dis[maxid]=0;
else {
ans-=maxi*K;
break;
}
}else{
if(K>mingap[maxid]){
ans-=maxi*mingap[maxid],K-=mingap[maxid],dis[maxid]-=mingap[maxid];
}else {
ans-=maxi*K;
break;
}
build_block(bid,tail[bid]);
}
}
printf("%d\n",ans);
}
int main(){
init();
solve();
return 0;
}