#include #define fi first #define se second #define rep(i,s,n) for (int i = (s); i < (n); ++i) #define rrep(i,g,n) for (int i = (n)-1; i >= (g); --i) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define len(x) (int)(x).size() #define dup(x,y) (((x)+(y)-1)/(y)) #define pb push_back #define eb emplace_back #define Field(T) vector> using namespace std; using ll = long long; using ull = unsigned long long; template using pq = priority_queue,greater>; using P = pair; templatebool chmax(T&a,T b){if(abool chmin(T&a,T b){if(b a) { vector>> dp(n+1, vector>(b, vector(c, -1))); dp[0][0][0] = 0; rep(i,0,n) rep(j,0,b) rep(k,0,c) if (dp[i][j][k] != -1) { if (j+1 < b) chmax(dp[i+1][j+1][0], dp[i][j][k]); if (k+1 < c) chmax(dp[i+1][0][k+1], dp[i][j][k]+a[i]); } ll ans = -1; rep(j,0,b) rep(k,0,c) ans = max(ans, dp[n][j][k]); rep(i,0,n+1) { rep(j,0,b) cout << dp[i][j][0] << " "; cout << ": "; rep(k,0,c) cout << dp[i][0][k] << " "; cout << endl; } cout << ans << endl; } int main() { int n, b, c; cin >> n >> b >> c; vector a(n); rep(i,0,n) cin >> a[i]; // jikken(n, b, c, a); vector vb(n+1, -1), vc(n+1, -1); vb[0] = vc[0] = 0; multiset stb, stc; stb.emplace(0), stc.emplace(0); ll val = 0; rep(i,0,n) { vb[i+1] = (*stc.rbegin())+val; vc[i+1] = (*stb.rbegin())-val; val += a[i]; if (i == 0) stb.clear(), stc.clear(); stb.emplace(vb[i+1]), stc.emplace(vc[i+1]); if (len(stb) >= b) stb.erase(stb.find(vb[i-b+2])); if (len(stc) >= c) stc.erase(stc.find(vc[i-c+2])); // for (ll e : stb) cout << e << " "; // cout << endl; } cout << max((*stb.rbegin()), (*stc.rbegin())+val) << endl; return 0; }