mickypinata

TUMSO18: Sneaky Getaway

Jul 23rd, 2021
898
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long lli;
  5.  
  6. const int N = 1e5;
  7.  
  8. lli qsum[N + 1];
  9.  
  10. int main(){
  11.  
  12.     int nDay, tr;
  13.     scanf("%d%d", &nDay, &tr);
  14.     tr /= 2;
  15.     for(int i = 1; i <= nDay; ++i){
  16.         scanf("%d", &qsum[i]);
  17.         qsum[i] = qsum[i] - tr + qsum[i - 1];
  18.     }
  19.     vector<lli> connect(1, 0);
  20.     int dp = 0;
  21.     for(int i = 1; i <= nDay; ++i){
  22.         if(qsum[i] <= 0){
  23.             continue;
  24.         }
  25.         int idx = lower_bound(connect.begin(), connect.end(), qsum[i]) - connect.begin();
  26.         if(idx == (int)connect.size()){
  27.             connect.push_back(0);
  28.         }
  29.         dp = idx;
  30.         connect[idx] = qsum[i];
  31.     }
  32.     cout << dp;
  33.  
  34.     return 0;
  35. }
  36.  
RAW Paste Data