The problem 44E has a DP tag. I tried to find a solution using DP for it but was hitting a dead end and no one seems to have done it with that approach.

It would be a great help if someone could try and solve through this approach.

My DP code for the question https://codeforces.com/problemset/problem/1189/C is given below. The answer for the first test case is giving 3 1 0 on my pc and ideone but 1 1 0 on codeforces. Im unable to find how the index is going out of bounds which might be causing the error. otherwise it's something totally new.

Please Help.

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
 #include <bits/stdc++.h>
using namespace std;
//using namespace __gnu_pbds;
using namespace std::chrono; 

#define int               long long
#define ld                long double
#define mod1              1000000007
#define mod2              998244353
#define pi               3.14159265358979323846
//#define hs                100006
#define inf               1e18
#define ninf              -1*(1e18)
#define pb                push_back
#define mp                make_pair
#define all(x)            (x).begin(),(x).end()
#define fi                first
#define se                second
#define vc                vector
#define pii               pair<int,int>
#define msi               map<string,int>
#define mii               map<int,int>
#define psi               pair<string,int>
#define pis               pair<int,string>
#define endl              "\n"

#define rep(i,a,b)        for(int i=a;i<b;i++)
#define repe(i,a,b)       for(int i=a;i<=b;i++)
#define bac(i,a,b)        for(int i=a;i>b;i--)
#define bace(i,a,b)       for(int i=a;i>=b;i--)

#define ios               ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DECIMAL(n)        std::cout << std::fixed << std::setprecision(n)
#define SORT(v)           sort(all(v))
#define RSORT(v)          sort(all(v),greater<int>())
#define REVERSE(v)        reverse(ALL(v))
#define GCD(m,n)          __gcd(m,n)
#define LCM(m,n)          m*(n/GCD(m,n))
#define init(x,a)         memset(x,a,sizeof(x))
#define trav(a, x)        for(auto& a : x)
#define display(x)        trav(a,x) cout<<a<<" "; cout<<endl
#define pow(i,n)          (int)pow((int)i,n)
#define pow2(n)           ((int)1<<n)
 
void solve() 
{ 
    int n;
    cin>>n;
    vc<int> v(n);
    rep(i,0,n) cin>>v[i];
    int maxseg = n,maxtimes = (log(n))/(log(2))+1;
    pii dp[maxtimes][maxseg];
    rep(i,0,maxtimes){
        rep(j,0,maxseg)
            dp[i][j].fi=0,dp[i][j].se=0;
    }
    rep(i,0,n) dp[0][i].fi=0, dp[0][i].se = v[i];
    rep(i,1,maxtimes){
        int t = pow2(i);
        int lol = t/2;
        repe(j,0,n-t){
            dp[i][j].fi = dp[i-1][j].fi + dp[i-1][j+lol].fi;
            dp[i][j].fi+=((dp[i-1][j].se+dp[i-1][j+lol].se)/10);
            dp[i][j].se = (dp[i-1][j].se+dp[i-1][j+lol].se)%10;
        }
    }   
    int q;
    cin>>q;
    int l,r;
    rep(i,0,q){
        cin>>l>>r;
        int huh = r-l+1;
        int sz = log(huh)/log(2);
        cout<<dp[sz][l-1].fi<<endl;
    }
}
 
signed main(){
    ios
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    int q=1;
    //cin>>q;
    while(q--){
        solve();
    }

    return 0;
}