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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 #include #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define FORD(i, a, b) for(int i = (a); i >= (b); --i) #define VAR(v, i) __typeof(i) v=(i) #define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i) #define all(v) (v).begin(),(v).end() #define PII pair #define st first #define nd second #define pb push_back #define lint long long int #define VI vector #define debug(x) {cout <<#x <<" = " < v; lint pref[205]; lint dp[205][205][62]; lint dp2[205][62]; lint INF = 1e9*1LL*1e9; lint sum(int i, int j) { if (i > j) return 0; return pref[j] - ((i==0)? 0 : pref[i-1]); } // odpowiedz dla przedzialu [i,j) // z wagami [0,2^k-1] lint rob(int i, int j, int k) { if (dp[i][j][k] != -INF-1) return dp[i][j][k]; if (i == j) return 0; if (j-i > (1LL< 0 && (1LL< m) u--; u++; FOR(i,0,n+1) FOR(j,i,n+1) FOR(k,0,61) dp[i][j][k] = -INF-1; FOR(i,0,n+1) FOR(k,0,61) dp2[i][k] = -INF-1; printf("%lld\n", rob2(0,u)); } int main() { read(n); scanf("%lld", &m); FOR(i,0,n) { lint a; scanf("%lld", &a); v.pb(a); } pref[0] = v[0]; FOR(i,1,n) pref[i] = pref[i-1] + v[i]; brut(); }