fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define maxn 1000005
  7. #define FOR(i , a , b) for(int i = a ; i <= b; i++)
  8. #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  9. #define REP(i , a , b) for(int i = a ; i < b ; i++)
  10.  
  11. int n , t;
  12.  
  13. int d[maxn];
  14.  
  15. bool F(int k){
  16.     priority_queue<int,vector<int> , greater<int>> q;
  17.     FOR(i , 1 , k) q.push(d[i]);
  18.  
  19.     FOR(i , k + 1 , n){
  20.         int cur_time = q.top();
  21.         q.pop();
  22.         q.push(d[i] + cur_time);
  23.     }
  24.  
  25.     int max_time = 0;
  26.     while(!q.empty()){
  27.         int cur_time = q.top();
  28.         q.pop();
  29.         max_time = max(max_time , cur_time);
  30.     }
  31.     return max_time <= t;
  32. }
  33.  
  34. int main(){
  35.  
  36.     FAST;
  37.     cin >> n >> t;
  38.     FOR(i , 1 , n) cin >> d[i];
  39.  
  40.     int l = 0;
  41.     int r = n + 1;
  42.     while(r - l > 1){
  43.         int mid = (l + r) / 2;
  44.         if(F(mid)) r = mid;
  45.         else l = mid;
  46.     }
  47.  
  48.     cout << r;  
  49. }
  50.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/0ZNTMp
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!