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 80 81 82 83 84 85 86 87 `#include using namespace std; using lld = long long; const lld MAXN = 200; const lld MAXM = 60; const lld INF = 3e18; lld dp[MAXM+5][MAXN+5][MAXN+5]; lld dp2[MAXM+5][MAXN+5][MAXN+5]; vector a; lld S(lld b, lld e){ return a[e]-a[b-1ll]; } lld calc(lld m, lld b){ m &= (1ll< 0 && !(m&(1ll<> n >> m; m++; a.resize(n+1ll); for(lld i=1ll;i<=n;i++) cin >> a[i]; for(lld i=1ll;i<=n;i++) a[i] += a[i-1ll]; for(lld i=0;i<=MAXM;i++) for(lld j=1ll;j<=n;j++) for(lld k=j;k<=n;k++) dp2[i][j][k] = dp[i][j][k] = -INF; bool ok = false; for(lld b=0;b<=MAXM;b++) for(lld i=1ll;i<=n;i++){ dp[b][i][i] = max(0ll, (lld) b * S(i,i)); dp2[b][i][i] = (!ok ? -INF : max(0ll, calc(m,b) * S(i,i))); if(m&(1ll<<(b-1ll))) ok = true; } for(lld b=1ll;b<=MAXM;b++){ for(lld i=1ll;i<=n;i++) for(lld j=i+1ll;j<=n;j++) dp[b][i][j] = dp[b-1ll][i][j]; for(lld i=1ll;i<=n;i++) for(lld k=i;k