# c++ – Codeforces Round #727 (Div 2) B time limit exceeded

I try to solve some old Codeforces questions. The problem is;

Petya once wrote a sad love song and shared it to Vasya. The song is a
string consisting of lowercase English letters. Vasya made up q
song starting from the l-th letter to the r-th letter. Vasya considers
a substring made up from characters on this segment and repeats each
letter in the subsegment k times, where k is the index of the
corresponding letter in the alphabet. For example, if the question is
about the substring “abbcb”, then Vasya repeats letter ‘a’ once, each
of the letters ‘b’ twice, letter ‘c” three times, so that the
resulting string is “abbbbcccbb”, its length is 10. Vasya is
interested about the length of the resulting string.

Help Petya find the length of each string obtained by Vasya.

Input The first line contains two integers n and q (1≤n≤100000,
1≤q≤100000) — the length of the song and the number of questions.

The second line contains one string s — the song, consisting of n
lowercase letters of English letters.

Vasya’s questions are contained in the next q lines. Each line
contains two integers l and r (1≤l≤r≤n) — the bounds of the question.

Output Print q lines: for each question print the length of the string
obtained by Vasya.

An example of input-output: input 7 3 abacaba 1 3 2 5 1 7 output 4 7
11

First, I used c++ to solve with dynamic programming and it works, yet I am getting time error. Therefore, I need suggestions to decrease execution time. My code:

``````#include<bits/stdc++.h>

using namespace std;
#define PII pair<int,int>

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

map<char, int> alph;
string latin = "abcdefghijklmnopqrstuvwxyz";
for(int x = 0; x < (int)latin.length(); x++)
alph(latin(x)) = x + 1;

int n, q;
cin >> n >> q;
string s;
cin >> s;
vector<int> results;
map<string, int> memo;

for(int k = 0; k < q; k++){
int l,r, length;
length = 0;
cin >> l >> r;

if(memo.find(s.substr(l-1, r - l + 1)) == memo.end()){
for(int b= l-1; b < r; b++){
length += alph(s(b));
}
memo(s.substr(l-1, r - l + 1)) = length;
}
else
length = memo(s.substr(l-1, r - l + 1));
results.push_back(length);
}
for(auto b: results)
cout << b << "n";
}
``````

My notes:

1. I think that I can successfully implemented Dp to my code.
2. Naming the variables are according to problem requirements, not
arbitrarily.