1 const int N=2e6;
2 int lt[N],rt[N];
3 class Solution {
4 public:
5 int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
6 memset(rt,0,sizeof(rt));
7 memset(lt,0,sizeof(lt));
8 int n=fruits.size();
9 int l=-1,r=0;
10 vector<int>stl,str;
11 for(int i=0;i<n;i++)
12 {
13 if(fruits[i][0]<=startPos)l=i;
14 else break;
15 }
16 r=l+1;
17 int step=0,st=startPos,presum=0;
18 for(int i=l;i>=0;i--)
19 {
20 step+=st- fruits[i][0];
21 st=fruits[i][0];
22 if(step>k)break;
23 lt[step]=presum+fruits[i][1];
24 presum=lt[step];
25 stl.push_back(step);
26 }
27 step=0,st=startPos;
28 presum=0;
29 for(int i=r;i<n;i++)
30 {
31 step+=fruits[i][0]-st;
32 st=fruits[i][0];
33 if(step>k)break;
34 rt[step]=fruits[i][1]+presum;
35 presum=rt[step];
36 str.push_back(step);
37 }
38 int ans=0;
39 for(int i=0;i<=k;i++)
40 {
41 int ltpos,rtpos;
42 if(k-2*i>0)ltpos=upper_bound(stl.begin(),stl.end(),k-2*i)-stl.begin()-1;
43 if(k-2*i>0)rtpos=upper_bound(str.begin(),str.end(),k-2*i)-str.begin()-1;
44 int rn=(k-2*i>0)?rt[i]+(ltpos>=0?lt[stl[ltpos]]:0):0;
45 int ln=(k-2*i>0)?lt[i]+(rtpos>=0?rt[str[rtpos]]:0):0;
46 ans=max({rn,ln,rt[i],lt[i],ans});
47 }
48 return ans;
49 }
50 };