Untitled

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    long long minCost(string s, int encCost, int flatCost) {
        
        int n = s.size();

        /*
        -------------------------------------------------------
        Step 1: Prefix sum to count number of '1's in O(1)
        -------------------------------------------------------
        prefix[i] = number of sensitive elements ('1') in s[0..i]
        */
        vector<int> prefix(n, 0);
        for(int i = 0; i < n; i++){
            if(i > 0) prefix[i] = prefix[i-1];
            if(s[i] == '1') prefix[i]++;
        }

        /*
        -------------------------------------------------------
        Step 2: Generate all segments obtainable by valid splits
        -------------------------------------------------------
        A segment can only be split if its length is even.
        Each split divides the segment into two equal halves.

        segments will store every segment [l, r] generated.
        We expand layer by layer (like levels of splitting).
        */
        vector<pair<int,int>> segments;
        segments.push_back({0, n-1});

        /*
        dp[r][k] = cost of the segment that ends at index r
                   when we are at split level k
        */
        vector<vector<long long>> dp(n, vector<long long>(22, -1));

        int leftPtr = 0, rightPtr = 0;
        int stage = 0;

        while(true){

            bool stopFurtherSplits = false;

            for(int i = leftPtr; i <= rightPtr; i++){

                int l = segments[i].first;
                int r = segments[i].second;

                int length = r - l + 1;

                /*
                -----------------------------------------
                Count number of sensitive elements
                -----------------------------------------
                */
                int sensitiveCount = prefix[r];
                if(l > 0) sensitiveCount -= prefix[l-1];

                /*
                -----------------------------------------
                Compute cost for this segment
                -----------------------------------------
                If no sensitive elements → flatCost
                Otherwise → L * X * encCost
                */
                long long cost = flatCost;

                if(sensitiveCount > 0){
                    cost = 1LL * encCost * length * sensitiveCount;
                }

                dp[r][stage] = cost;

                /*
                -----------------------------------------
                If segment length is even → split further
                -----------------------------------------
                */
                if(length % 2 == 0){

                    int half = length / 2;

                    segments.push_back({l, l + half - 1});
                    segments.push_back({l + half, r});
                }
                else{
                    stopFurtherSplits = true;
                }
            }

            stage++;

            leftPtr = rightPtr + 1;
            rightPtr = segments.size() - 1;

            if(stopFurtherSplits) break;
        }

        /*
        -------------------------------------------------------
        Step 3: DP over prefix of string
        -------------------------------------------------------

        ans[i] = minimum cost to cover substring [0..i]

        For every split level j:
        segment size = n / (2^j)

        If dp[i][j] exists, we try extending from
        the previous segment.
        */
        vector<long long> ans(n, 1e16);

        for(int i = 0; i < n; i++){

            for(int j = 0; j < stage; j++){

                if(dp[i][j] == -1) continue;

                long long segmentSize = n / (1LL << j);

                long long previousCost = 0;

                if(i - segmentSize >= 0){
                    previousCost = ans[i - segmentSize];
                }

                ans[i] = min(ans[i], previousCost + dp[i][j]);
            }
        }

        return ans[n-1];
    }
};

/*
===========================================================
Complexity Analysis
===========================================================

Let n = length of string.

1) Prefix computation
   -------------------
   We compute prefix sum once.

   Time Complexity:  O(n)
   Space Complexity: O(n)


2) Segment generation
   -------------------
   Each split halves the segment size.

   Maximum splits possible = log2(n)

   At each level we generate at most n / segment_size segments,
   so the total number of segments across all levels is O(n).

   Time Complexity:  O(n)
   Space Complexity: O(n)


3) Dynamic Programming
   -------------------
   For each index we try all split levels.

   Total levels ≈ log2(n)

   Time Complexity:  O(n log n)
   Space Complexity: O(n log n)  (for dp table)


-----------------------------------------------------------

Final Complexity

Time Complexity:  O(n log n)

Space Complexity: O(n log n)

===========================================================
*/