Given string S of N (N<=100 000) characters (each character is digit). Also given, L and R (L <= R <= 109 ). Find maximum sum that is possible to obtain cutting the string in such a way that every part has value <=R and >=L.
Input: N L R S
Test case:
8 13 997
81196054
Output: 1825
Explanation: These are all possible cuts. Last cut is best
1. 81|19|60|54
2. 81|196|054
3. 811|96|054
4. 811|960|54
dp[i] = maximum answer on prefix. Every iteration, try all numbers with digits [i+1 ... r) and update dp[r]. r can't go far from i.
I don't understand the part with digits [i+1,r). Also r can be up to 1e9
It's not r from the statement. You may call it j. You move j to the right from i and try to add the number formed by the digits a[i] ... a[j]. As L, R <= 1e9, j — i <= 10.
Yes that's what i did but going to left so i couldn't handle big number of leading zeros. Thank you
Nevermind