fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
  4. #define ll long long
  5. #define max(a, b) (a > b ? a : b)
  6. string s;
  7. ll dp[210];
  8.  
  9. ll dfs(int idx) {
  10.     if (idx == s.size()) return 0;
  11.     else if (dp[idx] != -1) return dp[idx];
  12.     else {
  13.         ll partialSum = 0, totalSum = 0;
  14.         for (int i = idx; i < s.size(); i++) {
  15.             partialSum *= 10;
  16.             partialSum += (s[i] - '0');
  17.             if (partialSum > INT_MAX) break;
  18.             totalSum = max(totalSum, partialSum + dfs(i + 1)); 
  19.         }
  20.         return dp[idx] = totalSum;
  21.     }
  22. }
  23.  
  24. int main() {
  25.     fastio;
  26.     int n;
  27.     cin >> n;
  28.     while(n--) {
  29.         fill(dp, dp + 210, -1);
  30.         cin >> s;
  31.         cout << dfs(0) << endl;
  32.     }
  33.     return 0;
  34. }
Success #stdin #stdout 0.01s 5548KB
comments (?)
stdin
copy 
6
1234554321
5432112345
000
121212121212
2147483648
11111111111111111111111111111111111111111111111111111
stdout
copy 
1234554321
543211239
0
2121212124
214748372
5555555666
https://ideone.com/WzVa1J
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!