\documentclass{article} \usepackage{geometry} \usepackage{graphicx} \usepackage{listings} \usepackage{xcolor}

\geometry{a4paper, margin=1in}

\title{Codeforces Blog Title} \author{Your Codeforces Handle} \date{\today}

\begin{document}

\maketitle

\section*{Introduction} Brief introduction about the problem, your approach, and any interesting observations.

\section*{Problem Statement} Provide the problem statement or a summary of the problem you solved.

\section*{Solution} Include your code or algorithm here with explanations.

\begin{lstlisting}[language=C++, caption=Your Code Here] // Your code goes here \end{lstlisting}

\section*{Complexity Analysis} Analyze the time and space complexity of your solution.

\section*{Testing and Edge Cases} Describe the test cases you used to validate your solution. Highlight any edge cases you considered.

\section*{Conclusion} Summarize your approach and any lessons learned from solving the problem.

\section*{Visualizations (Optional)} Include any relevant charts, graphs, or visualizations if applicable.

\section*{Acknowledgments} Give credit to any resources, articles, or discussions that helped you in solving the problem.

\section*{Closing Thoughts} Share any additional thoughts or reflections on the problem-solving process.

\section*{Appendix (Optional)} Include any additional information, references, or supplementary materials.

\end{document}

#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n;
  cin >> n;
  int arr[n];
  for(int i = 0; i < n; i++){
    cin >> arr[i];
  }
 
  long long int sum = 0;
  for(int i = 0; i < n; i++){
    sum += arr[i];
  }
 
  long long int ans = sum - n;
  cout << ans << "\n";
}

Given an array $$$a$$$ of integers, we aim to efficiently process multiple queries. For each query, we calculate $$$c$$$, representing the count of all elements in the subsegment $$$[a_l, a_r]$$$.

To optimize this process, we compute the prefix sums of the binary representation of array elements in O $$$(n \log(\max(a)))$$$. The array $$$Pre[i][j]$$$ denotes the count of $$$j$$$-th bits in the binary representation of the first $$$i$$$ elements of $$$a$$$.

For each query, we identify bits present in all elements of $$$[a_l, a_r]$$$ by checking $$$Pre[r][j] - Pre[l-1][j] = r - l + 1$$$ for each bit $$$j$$$. If true, the $$$j$$$-th bit is set in the result.

Utilizing a difference array for XOR, we create array $$$b$$$. For each query, $$$b[l] = c$$$ and $$$b[r+1] = c$$$. After all queries, we XOR the prefix sum of $$$b$$$ with elements of $$$a$$$.

The final result is stored in array $$$ans$$$, where $$$ans[i]$$$ reflects the result after processing queries up to the $$$i$$$-th element.

#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int n;
  cin >> n;
  int v[n];
  for(int i = 0; i < n; i++) cin >> v[i];
 
  int pre[n+1][30];
  for(int i = 0; i < 30; i++) pre[0][i] = 0;
 
  for(int i = 0; i < n; i++){
    for(int j = 0; j < 30; j++){
      pre[i+1][j] = pre[i][j];
      pre[i+1][j] += ((v[i] >> j) & 1); 
    }
  }
 
  int q;
  cin >> q;
  int ans[n] = {0};
  while(q--){
    int l, r;
    cin >> l >> r;
    int result = 0;
    for(int i = 0; i < 30; i++){
      if(pre[r][i] - pre[l-1][i] == r - l + 1){
        result |= (1 << i);
      }
    }
 
    ans[l-1] ^= result;
    if(r != n)
    ans[r] ^= result;
  }
 
  for(int i = 1; i < n; i++){
    ans[i] ^= ans[i-1];
  }
 
  for(int i = 0; i < n; i++){
      ans[i] ^= v[i];
    cout << ans[i] << " ";
  }
  cout << "\n";
}

We are solving the problem by utilizing Dynamic Programming. Let $$$dp[i]$$$ represent the maximum sum achievable when considering the substring from $$$s[0]$$$ to $$$s[i]$$$. For each $$$i$$$ from $$$0$$$ to $$$n-1$$$, we iterate through the previous $$$k$$$ positions and calculate the Maximum sum if we place a '+' sign at that position. The idea is to find the optimal placement of '+' signs to aximize the sum.

So, the recursive relation is defined as follows: $$$dp[i] = \max(dp[i - j] + (s[i - j] - $$$'0'$$$))$$$ where the maximum is taken over all valid values of $$$j$$$ (from $$$1$$$ to $$$k$$$), and we ensure that the index $$$i - j$$$ is within bounds.

The final result is given by $$$dp[n - 1]$$$, which represents the maximum sum achievable considering the entire string. This dynamic programming approach efficiently explores all possible placements of '+' signs and computes the maximum sum.

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

typedef long long ll;

const ll inf = 1e18;

ll rev(ll i, string &s, vector<ll> &dp, ll k) {
    if (dp[i] != -1)
        return dp[i];

    ll mx = INT_MIN;
    ll curr = s[i] - '0';
    ll p = 10;
    for (ll j = 1; j <= k; j++) {
        if (i - j >= 0) {
            mx = max(mx, rev(i - j, s, dp, k) + curr);
            curr = (s[i - j] - '0') * p + curr;
            p *= 10;
        } else {
            mx = max(mx, curr);
            break;
        }
    }

    return dp[i] = mx;
}

void solve() {
    ll n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<ll> dp(n, -1);
    rev(n - 1, s, dp, k);
    cout << dp[n - 1] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll t = 1;
    for (ll T = 1; T <= t; T++) {
        solve();
    }
    return 0;
}