//#include "/Users/dimazhylko/CPPProjects/bits/stdc++.h" #include <bits/stdc++.h> #include "kanapka.h" using namespace std; typedef long long ll; typedef long double ld; int main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); ll N; N = GetN(); ll res = 0; vector<ll> A(N); ll mf = 0; ll me = 0; for(ll i = 0;i<N;i++){ A[i] = GetTaste(i); } vector<ll> F(N+1, 0); vector<ll> E(N+1, 0); ll s = 0; vector<ll> f; for(int i = 1;i<=N;i++){ s+=A[i-1]; if(s>F[i-1]){ mf = i; f.push_back(mf); } F[i]=max(F[i-1], s); } s=0; vector<ll> e; for(int i = N;i>0;i--){ s+=A[i-1]; if(s>E[N-i]){ me=i; e.push_back(me); } E[N-i+1]=max(E[N-i],s); } if(mf<me){ cout<<F[N]+E[N]<<endl; } else { if(F[N]>E[N]){ res = F[N]; for(int i = e.size()-1;i>=0;i--){ if(e[i]>mf){ res+=E[N-e[i]+1]; break; } } } else { res = E[N]; for(int i = f.size()-1;i>=0;i--){ if(f[i]<mf){ res+=E[f[i]]; break; } } } cout<<res<<endl; } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | //#include "/Users/dimazhylko/CPPProjects/bits/stdc++.h" #include <bits/stdc++.h> #include "kanapka.h" using namespace std; typedef long long ll; typedef long double ld; int main(){ ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); ll N; N = GetN(); ll res = 0; vector<ll> A(N); ll mf = 0; ll me = 0; for(ll i = 0;i<N;i++){ A[i] = GetTaste(i); } vector<ll> F(N+1, 0); vector<ll> E(N+1, 0); ll s = 0; vector<ll> f; for(int i = 1;i<=N;i++){ s+=A[i-1]; if(s>F[i-1]){ mf = i; f.push_back(mf); } F[i]=max(F[i-1], s); } s=0; vector<ll> e; for(int i = N;i>0;i--){ s+=A[i-1]; if(s>E[N-i]){ me=i; e.push_back(me); } E[N-i+1]=max(E[N-i],s); } if(mf<me){ cout<<F[N]+E[N]<<endl; } else { if(F[N]>E[N]){ res = F[N]; for(int i = e.size()-1;i>=0;i--){ if(e[i]>mf){ res+=E[N-e[i]+1]; break; } } } else { res = E[N]; for(int i = f.size()-1;i>=0;i--){ if(f[i]<mf){ res+=E[f[i]]; break; } } } cout<<res<<endl; } return 0; } |