#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
class Solution{
public :
int furthestBuilding( vector< int > & H, int bricks, int ladders) {
int i;
int s = 0 ;
int sa;
priority_queue< int > q;
for ( i= ( 1 ) ; i< ( H.size ( ) ) ; i++ ) {
sa = H[ i] - H[ i- 1 ] ;
if ( sa <= 0 ) {
continue ;
}
q.push ( - sa) ;
if ( q.size ( ) > ladders) {
s + = - q.top ( ) ;
q.pop ( ) ;
if ( s > bricks) {
break ;
}
}
}
return i- 1 ;
}
}
;
// cLay varsion 20201101-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
// class Solution {
// public:
// int furthestBuilding(vector<int>& H, int bricks, int ladders) {
// int s = 0, sa;
// priority_queue<int> q;
// rep(i,1,H.size()){
// sa = H[i] - H[i-1];
// if(sa <= 0) continue;
// q.push(-sa);
// if(q.size() > ladders){
// s += -q.top();
// q.pop();
// if(s > bricks) break;
// }
// }
// return i-1;
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPZmFzdCIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbWFpbiBkdW1teV9tYWluCmludCBtYWluKCl7CiAgcmV0dXJuIDA7Cn0KI3VuZGVmIG1haW4KY2xhc3MgU29sdXRpb257CiAgcHVibGljOgogIGludCBmdXJ0aGVzdEJ1aWxkaW5nKHZlY3RvcjxpbnQ+JiBILCBpbnQgYnJpY2tzLCBpbnQgbGFkZGVycyl7CiAgICBpbnQgaTsKICAgIGludCBzID0gMDsKICAgIGludCBzYTsKICAgIHByaW9yaXR5X3F1ZXVlPGludD4gcTsKICAgIGZvcihpPSgxKTtpPChILnNpemUoKSk7aSsrKXsKICAgICAgc2EgPSBIW2ldIC0gSFtpLTFdOwogICAgICBpZihzYSA8PSAwKXsKICAgICAgICBjb250aW51ZTsKICAgICAgfQogICAgICBxLnB1c2goLXNhKTsKICAgICAgaWYocS5zaXplKCkgPiBsYWRkZXJzKXsKICAgICAgICBzICs9IC1xLnRvcCgpOwogICAgICAgIHEucG9wKCk7CiAgICAgICAgaWYocyA+IGJyaWNrcyl7CiAgICAgICAgICBicmVhazsKICAgICAgICB9CiAgICAgIH0KICAgIH0KICAgIHJldHVybiBpLTE7CiAgfQp9CjsKLy8gY0xheSB2YXJzaW9uIDIwMjAxMTAxLTEKCi8vIC0tLSBvcmlnaW5hbCBjb2RlIC0tLQovLyAjZGVmaW5lIG1haW4gZHVtbXlfbWFpbgovLyB7fQovLyAjdW5kZWYgbWFpbgovLyAKLy8gY2xhc3MgU29sdXRpb24gewovLyBwdWJsaWM6Ci8vICAgaW50IGZ1cnRoZXN0QnVpbGRpbmcodmVjdG9yPGludD4mIEgsIGludCBicmlja3MsIGludCBsYWRkZXJzKSB7Ci8vICAgICBpbnQgcyA9IDAsIHNhOwovLyAgICAgcHJpb3JpdHlfcXVldWU8aW50PiBxOwovLyAgICAgcmVwKGksMSxILnNpemUoKSl7Ci8vICAgICAgIHNhID0gSFtpXSAtIEhbaS0xXTsKLy8gICAgICAgaWYoc2EgPD0gMCkgY29udGludWU7Ci8vICAgICAgIHEucHVzaCgtc2EpOwovLyAgICAgICBpZihxLnNpemUoKSA+IGxhZGRlcnMpewovLyAgICAgICAgIHMgKz0gLXEudG9wKCk7Ci8vICAgICAgICAgcS5wb3AoKTsKLy8gICAgICAgICBpZihzID4gYnJpY2tzKSBicmVhazsKLy8gICAgICAgfQovLyAgICAgfQovLyAgICAgcmV0dXJuIGktMTsKLy8gICB9Ci8vIH07Cg==