1703G - Good Key Bad Key - CodeForces Solution

bitmasks brute force dp greedy math *1600

Please click on ads to support us..

Python Code: 

from itertools import accumulate as ac;r=lambda:map(int,input().split());t,=r();f=lambda i:p[i]-k*i+sum(a[i+j]>>(j+1)for j in range(min(n-i,30)))
while t:t-=1;n,k=r();a=[*r()];p=[0]+list(ac(a));print(max(f(i)for i in range(n+1)))

C++ Code: 

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

void solve() {
    int n, k;
    cin >> n >> k;

    vector<ll> a(n);
    for (auto &x: a) cin >> x;

    vector<vector<ll>> dp(n + 1, vector<ll>(31, -1e18));
    dp[0][0] = 0;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= min(i + 1, 30); j++) {
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] - k + (a[i] / (1 << j)));
            int nxt = min(30, j + 1);
            dp[i + 1][nxt] = max(dp[i + 1][nxt], dp[i][j] + (a[i] / (1 << nxt)));
        }
    }

    cout << *max_element(dp[n].begin(), dp[n].end());
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;

    while (t--) {
        solve();
        cout << '\n';
    }
}


Comments

Submit
0 Comments
More Questions

25B - Phone numbers
1633C - Kill the Monster
1611A - Make Even
1030B - Vasya and Cornfield
1631A - Min Max Swap
1296B - Food Buying
133A - HQ9+
1650D - Twist the Permutation
1209A - Paint the Numbers
1234A - Equalize Prices Again
1613A - Long Comparison
1624B - Make AP
660B - Seating On Bus
405A - Gravity Flip
499B - Lecture
709A - Juicer
1358C - Celex Update
1466B - Last minute enhancements
450B - Jzzhu and Sequences
1582C - Grandma Capa Knits a Scarf
492A - Vanya and Cubes
217A - Ice Skating
270A - Fancy Fence
181A - Series of Crimes
1638A - Reverse
1654C - Alice and the Cake
369A - Valera and Plates
1626A - Equidistant Letters
977D - Divide by three multiply by two
1654B - Prefix Removals