fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. vector<vector<int>> dp;
  5.  
  6. int solve(string &x, int y, int idx) {
  7.   if (y < 0) return 1000;
  8.   if (idx == x.length()) return (y == 0 ? 0 : 1000);
  9.  
  10.   if (dp[idx][y] != -1) return dp[idx][y];
  11.  
  12.   int ans = 1000;
  13.   for (int i = idx; i < min(idx + 4, (int )x.length()); i++) {
  14.  
  15.     int num = stoi(x.substr(idx, i - idx + 1));
  16.  
  17.     ans = min(ans, solve(x, y - num, i + 1) + (i < x.length() - 1));
  18.  
  19.   }
  20.  
  21.   return dp[idx][y] = ans;
  22. } 
  23.  
  24. int main() {
  25.   string x; cin >> x;
  26.   int y; cin >> y;
  27.   int n = x.length();
  28.   dp = vector<vector<int>> (n, vector<int> (y + 1, -1));
  29.   int ans = solve(x, y, 0);
  30.   if (ans == 1000) cout << -1;
  31.   else cout << ans;
  32.   return 0;
  33. }
Success #stdin #stdout 0.01s 5368KB
comments (?)
stdin
copy 
111
12
stdout
copy 
1
https://ideone.com/r8QQNT
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!