A83464.上课不要睡觉
普及/提高-
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
你和朋友 Mishka 正在上微积分课,这节课一共持续 n 分钟。第 i 分钟老师会讲 ai 条定理。
给定一个长度为 n 的数组 t 来描述 Mishka 每分钟的状态:
- 若在第 i 分钟他睡着,则 ti=0;
- 若清醒,则 ti=1。
当他清醒时,会把这一分钟老师讲的定理全部记下来(获得 ai 的“收益”);当他睡着时,这一分钟就什么也记不到。
你掌握一种秘密技巧,能让 Mishka 连续保持清醒恰好 k 分钟,但只能使用一次。你可以选择在任意一分钟的开始启动它(只要完整的 k 分钟区间没有超出整节课范围)。在这段被技巧覆盖的区间里,无论原本他是否会睡着,都将视为清醒并获得相应的 ai。
请计算:如果你把这项技巧使用在最合适的时段,Mishka 最多能记下多少条定理。
输入格式
第一行:两个整数 n,k。
第二行:n 个整数 a1,a2,…,an。
第三行:n 个整数 t1,t2,…,tn(仅为 0 或 1)。
输出格式
一行一个整数,表示在最优使用这项技巧的前提下,Mishka 最多能记下的定理总数。
输入输出样例
输入#1
6 3 1 3 5 2 5 4 1 1 0 1 0 0
输出#1
16
说明/提示
1≤k≤n≤105
1≤ai≤104
0≤ti≤1
对于样例:
原本清醒的分钟会直接获得对应的 ai;而你可以选择一个长度为 k=3 的连续区间把他“强制清醒”。若从第 3 分钟开始使用(覆盖第 3–5 分钟),则:
原本清醒得到的和:第 1、2、4 分钟 → 1+3+2=6;
叫醒区间中原本会睡着的分钟也能获得:第 3、5 分钟 → 5+5=10;
合计 6+10=16,这是最优方案。