o079. 4. 最佳選擇 -- 2024年6月APCS | From: [118.169.85.150] | 發表日期 : 2024-06-29 22:31

# include <bits/stdc++.h>

using namespace std;

 

int n,m,ans=0;  

vector<int> v(300050), v_r(300050),vpr(300050,0),v_rpr(300050,0);

vector<int> lp(300050,0), rp(300050,0);  // odd-even

map<int,vector<int>> mp;

 

int main()

{

cin >> n >> m;

for (int i=1; i<=n; i++)  {cin >> v[i];  v_r[n-i+1] = v[i];}

 

for (int i=1; i<=n; i++){

if (v[i]&1)    lp[i] = lp[i-1]+1;

else           lp[i] = lp[i-1]-1;

 

if (v_r[i]&1)  rp[i] = rp[i-1]+1;

else           rp[i] = rp[i-1]-1;

 

vpr[i] = vpr[i-1]+v[i];

v_rpr[i] = v_rpr[i-1]+v_r[i];

mp[rp[i]].push_back(v_rpr[i]);

}

/*

for (int i=1; i<=n; i++)  cout << vpr[i] << " ";  cout << '\n';

for (int i=1; i<=n; i++)  cout << v_rpr[i] << " ";  cout << '\n';

for (int i=1; i<=n; i++)  cout << lp[i] << " ";  cout << '\n';

for (int i=1; i<=n; i++)  cout << rp[i] << " ";  cout << '\n';

*/

int ans=0;

for (int i=1; i<=n; i++){

    if (vpr[i]>m)  break;

    

    for (auto k : mp[0-lp[i]]){

        if (k+vpr[i]<=m)  ans=max(ans,k+vpr[i]);

        else              break;

    }

}

cout << ans << '\n';

    

return 0;

}