746F - Music in Car - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

int N , W , K;
vector<int> A;
vector<int> T;

long long f(){
//	cout << ".";
	multiset<int> Mx;
	multiset<int> Mn;
	int L = 0;
	int R = 0;
	long long time = 0;
	long long sum = 0;
	long long res = 0;
//	int superSum = 0;
	
//	cout << ".";
	while(true){
		while(true){
//			cout << "....";
			
			if(R >= N){
//				cout << "...";
				break;
			}
			if(Mx.empty() == true or Mx.size() < W){
//				cout << "..";
				time += (T[R] + 1) / 2;
				if(time > K){
					time -= (T[R] + 1) / 2;
					
					break;
				}
				sum += A[R];
//				cout << sum << "--";
				Mx.insert(T[R]);
				R++;
			}else if(T[R] <= *Mx.begin()){
//				cout << "...";
				time += T[R];
				if(time > K){
					time -= T[R];
					break;
				}
				sum += A[R];
				Mn.insert(T[R]);
				R++;
			}else{
//				cout << "....";
				time += (T[R] + 1) / 2;
				time += *Mx.begin() - (*Mx.begin() + 1) / 2;
				if(time > K){
					time -= (T[R] + 1) / 2;
					time -= *Mx.begin() - (*Mx.begin() + 1) / 2;
					break;
				}
				sum += A[R];
				Mn.insert(*Mx.begin());
				Mx.erase(Mx.begin());
				Mx.insert(T[R]);
				R++;
			}
		}
		
		if(sum > res){
			res = sum;
			if(L > 100000 and N == 200000){
				cout << L << " : " << sum << "\n";
			}
		}
		if(L == 200 and N == 200000){
//			cout << L << " : " << sum << "\n";
		}
		
//		cout << L << " : " << sum << " --> " << time << "\n";
		_Rb_tree_const_iterator<int> d = Mx.find(T[L]);
		if(Mx.empty() == false and d != Mx.end()){
			time -= (T[L] + 1) / 2;
			Mx.erase(d);
			if(Mn.empty() == false){
				_Rb_tree_const_iterator<int> d2 = Mn.end();
				d2--;
				Mx.insert((*d2));
				time += (*d2 + 1) / 2 - *d2;
				Mn.erase(d2);
			}
		}else if(Mn.empty() == false){
			time -= T[L];
			Mn.erase(Mn.find(T[L]));
		}
		
		sum -= A[L];
		L++;
		
		if(L >= R){
			R = L;
			sum = 0;
			time = 0;
			Mn.clear();
			Mx.clear();
		}
		if(L >= N){
			break;
		}
	}
	
	return res;
}

int main(){
//	ios_base::sync_with_stdio(false);
//    cin.tie(0);
    
    cin >> N >> W >> K;
    for(int i = 0 ; i < N ; i++){
    	int d;
    	cin >> d;
    	A.push_back(d);
	}
	for(int i = 0 ; i < N ; i++){
		int d;
		cin >> d;
		T.push_back(d);
	}
	
//	cout << "/";
	cout << f();
}