//Krzysztof Boryczka #pragma GCC optimize "O3" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; const int inf=0x3f3f3f3f; const ll INF=0x3f3f3f3f3f3f3f3f; #define FOR(i, b, e) for(int i=b; i<=e; i++) #define FORD(i, b, e) for(int i=b; i>=e; i--) #define SIZE(x) ((int)x.size()) #define pb push_back #define st first #define nd second #define sp ' ' #define ent '\n' const int M=61; const int N=205; ll dp[N][N][M+2], wdp[N][N][M+2]; ll t[N], pref[N]; ll m; int n; ll sum(int a, int b){ if(a>b) return 0; return pref[b]-pref[a-1]; } int bity(ll k){ int bits=0; while(1ll<<bits <= k) bits++; return bits; } int drugy(ll val){ return bity(val^(1ll<<(bity(val)-1))); } void solve(){ cin>>n>>m; FOR(i, 1, n) cin>>t[i]; FOR(i, 1, n) pref[i]=pref[i-1]+t[i]; FOR(i, 1, n) FOR(j, i+1, n) wdp[i][j][0]=dp[i][j][0]=-INF; FOR(k, 1, M) FOR(i, 1, n) FOR(j, i, n){ dp[i][j][k]=-INF; FOR(l, i, j+1) dp[i][j][k]=max(dp[i][j][k], dp[i][l-1][k-1]+dp[l][j][k-1]+sum(l, j)); } FOR(k, 1, M) FOR(i, 1, n) FOR(j, i, n){ wdp[i][j][k]=-INF; ll suff=((1ll<<k)-1)&m; if(((1ll<<(k-1))&suff) == 0) continue; int drugi=drugy(suff); FOR(l, i, j+1) wdp[i][j][k]=max(wdp[i][j][k], dp[i][l-1][k-1]+wdp[l][j][drugi]+sum(l, j)); } cout<<wdp[1][n][bity(m)]<<ent; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // int tt; cin>>tt; // FOR(te, 1, tt) solve(); 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 | //Krzysztof Boryczka #pragma GCC optimize "O3" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<int, int> ii; typedef vector<int> vi; typedef vector<ii> vii; const int inf=0x3f3f3f3f; const ll INF=0x3f3f3f3f3f3f3f3f; #define FOR(i, b, e) for(int i=b; i<=e; i++) #define FORD(i, b, e) for(int i=b; i>=e; i--) #define SIZE(x) ((int)x.size()) #define pb push_back #define st first #define nd second #define sp ' ' #define ent '\n' const int M=61; const int N=205; ll dp[N][N][M+2], wdp[N][N][M+2]; ll t[N], pref[N]; ll m; int n; ll sum(int a, int b){ if(a>b) return 0; return pref[b]-pref[a-1]; } int bity(ll k){ int bits=0; while(1ll<<bits <= k) bits++; return bits; } int drugy(ll val){ return bity(val^(1ll<<(bity(val)-1))); } void solve(){ cin>>n>>m; FOR(i, 1, n) cin>>t[i]; FOR(i, 1, n) pref[i]=pref[i-1]+t[i]; FOR(i, 1, n) FOR(j, i+1, n) wdp[i][j][0]=dp[i][j][0]=-INF; FOR(k, 1, M) FOR(i, 1, n) FOR(j, i, n){ dp[i][j][k]=-INF; FOR(l, i, j+1) dp[i][j][k]=max(dp[i][j][k], dp[i][l-1][k-1]+dp[l][j][k-1]+sum(l, j)); } FOR(k, 1, M) FOR(i, 1, n) FOR(j, i, n){ wdp[i][j][k]=-INF; ll suff=((1ll<<k)-1)&m; if(((1ll<<(k-1))&suff) == 0) continue; int drugi=drugy(suff); FOR(l, i, j+1) wdp[i][j][k]=max(wdp[i][j][k], dp[i][l-1][k-1]+wdp[l][j][drugi]+sum(l, j)); } cout<<wdp[1][n][bity(m)]<<ent; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // int tt; cin>>tt; // FOR(te, 1, tt) solve(); return 0; } |