田园将芜胡不归？既自以心为形役，奚惆怅而独悲？悟已往之不谏，知来者之可追。实迷途其未远，觉今是而昨非。
题目链接http://codeforces.com/contest/746/problem/F
cf div2 386,稍微纪念一下，终于变为blue，然而还是2道题的水平！先说一下这次的大体情况吧！这次是什么比赛的同步，一般这个比赛的题目都比较水，就像这次一样，拿下4,5题不是问题！然而普通的div2，就没有这么好的条件了，真是冲分的好机会！这次做了4题，都是读完题，就有思路，稍微思考一下边界条件，然后码代码就可以了！然后，d题怎么也过不去，后来分析是没有仔细思考，一是枚举的方式不太好，二是这种的边界不好处理！然后就去码e题，居然一次就过了，但是后怕system test会挂，后来听说这题的checker有问题，算是水过了！然后再看了看d题，就没时间了！f题和g题，都没有看！
后来看了下f和g题，g题跟以前的一道题目很相似，然后画了画简单例子，码完就过了。f题实在没什么思路！
这里写一下看完f题的想法，或者是为什么无从下手的原因，或者是什么困惑：
1. 数据范围很大，n=2e5,k=1e9，如果考虑用dp的话，这个数据范围不行啊，考虑dp的原因是：因为不知道那些歌曲该取半，哪些不该取半！
2. 看完官方题解和讨论后，感觉上面的考虑就是扯淡，根本一点关联也没有！
原因是：a. 听的歌曲可以从任意位置开始
b. k时间内听得歌曲都必须听，不能跳过（而这点就限制了，解题思路不能往dp方向考虑，而是区间）
c. 最关键的是：这里固定区间，使得收益最大，（每首歌曲的收益都是正数，没有负数和0，而且听的时间减半也不会对收益造成影响），那么收益最大就是听尽可能多的歌曲，那么，很容易得出结论，（这个题目的限制条件，取半的歌曲的数目上限为w），寻找区间，使得区间内听歌时间最大的w个的歌曲取半，这样得到的是这个区间的最大收益值，这样结果很明确，不容考虑各种组合，不需要枚举，不需要dp，（反正这里也不能dp），最优的也就那么一种。
d. 最终的答案就是遍历所有可能这样区间即可，固定左边界，右边界是非递减的，这就可以使用two pointer来做！
3. 接下来就是码代码，知道思想以后，还有一条鸿沟，就是考虑使用什么数据结构，ac了才是王道。
4. 一开始看题，是在想不明白这题的tag是data structure,现在恍然大悟。
5. 思路里面还有一个小细节，删除的时候需要考虑的，这题还是有一定难度的。质量很高！
这里贴一个别人的代码：写的很清晰，简单，漂亮！
/* Author haleyk10198 */
/* �@��: haleyk10198 */
#include <bits/stdc++.h> #define MOD 1000000007
#define LINF (1LL<<60)
#define INF 2147483647
#define PI 3.1415926535897932384626433
#define ll long long
#define pii pair<int,int>
#define mp(x,y) make_pair((x),(y)) using namespace std; string itos(int x){
stringstream ss;
ss<<x;
return ss.str();
} int n, m, k, a[], b[], tt, res, now; set<pii> h1, h2; int main(){
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
ios_base::sync_with_stdio(false);
cin >> n >> m >> k;
for(int i = ; i < n; i++)
cin >> a[i];
for(int i = ; i < n; i++)
cin >> b[i];
for(int l = , r = ; r < n; ){
while(tt <= k && r < n){
if(h1.size() < m){
h1.insert(mp(b[r], r));
tt += (b[r] + ) / ;
}
else if(h1.begin()->first < b[r]){
tt -= (h1.begin()->first + ) / ;
tt += h1.begin()->first;
tt += (b[r] + ) / ;
h2.insert(*h1.begin());
h1.erase(*h1.begin());
h1.insert(mp(b[r], r));
}
else{
h2.insert(mp(b[r], r));
tt += b[r];
}
now += a[r++];
if(tt <= k)
res = max(res, now);
}
while(tt > k){
if(h1.count(mp(b[l], l))){
tt -= (b[l] + ) / ;
h1.erase(mp(b[l], l));
if(!h2.empty()){
auto x = *h2.rbegin();
tt -= x.first;
tt += (x.first + ) / ;
h1.insert(x);
h2.erase(x);
}
}
else{
tt -= b[l];
h2.erase(mp(b[l], l));
}
now -= a[l++];
if(tt <= k)
res = max(res, now);
}
}
cout << res << endl;
return ;
}