Problem 1237 : Shredding Company

Problem F: Shredding Company
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1237

• 問題概要

６桁までの数字が書いた紙が与えられる。この紙を好きに分割して、それらの合計の数をつくる。
それが与えられた数にできるだけ近くであり、かつその数字を超えないものをつくれ。
その数字と、どのように分割したか答えよ。

• 解法

全探索。

• ソース

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<sstream>
#include<cassert>
#include<queue>
#include<stack>

#define REP(i,b,n) for(int i=b;i<n;i++)
#define rep(i,n)   REP(i,0,n)
#define ALL(C)     (C).begin(),(C).end()
#define pb         push_back
#define mp         make_pair
#define vint       vector<int>
#define FOR(it,o)  for(__typeof((o).begin()) it=(o).begin(); it!=(o).end(); ++it)
#define lli	    long long int
#define ld	    long double

using namespace std;

string s;
int t, maxi;
bool reject;
vint ans;
void com(int sum, int pos, vint v){
  if(sum > t)return;
  if(pos == s.length()){
    if(maxi == sum){
      reject = true;
    }
    if(maxi < sum){
      reject = false;
      maxi = sum;
      ans = v;
    }
    return;
  }
  int tmp = s.length() - pos;
  rep(i, tmp){
    int tmpi = atoi(s.substr(pos, i+1).c_str());
    vint tmpv = v;
    tmpv.pb(tmpi);
    com(sum + tmpi, pos+i+1, tmpv);
  }
}
    
  


main(){

  while(cin >> t >> s){
    if(t == 0 && s == "0")break;
   
    maxi = -1;
    reject = false;
    
    com(0, 0, vint());
   
    if(reject){
      cout << "rejected" << endl;
    }
    else if(maxi == -1){
      cout << "error" <<endl;
    }
    else {
      cout << maxi;
      FOR(it, ans)cout << ' ' << (*it);
      cout << endl;
    }
  }
}

簡潔にかけた気がする。
substr()の辺で頭がこんがらがった。