Go: package main

import (
	"bufio"
	"os"
	"strings"
	"strconv"
	"fmt"
	)

var scanner = bufio.NewScanner(os.Stdin)
const MAX_WIDTH = 1500000

func main() {
	// 二分探索で探す
	// 二分探索はソート済みの配列に対して、特定の条件を満たす値を
	// 効率よく選択するアルゴリズム
	for scanner.Scan() {
		buf := strings.Split(scanner.Text(), " ")
		m, _ := strconv.Atoi(buf[0])
		n, _ := strconv.Atoi(buf[1])
		if n == 0 && m == 0 {
			break
		}
		books := make([]int, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			books[i], _ = strconv.Atoi(scanner.Text())
		}
		check := func(width int) bool {
			// widthの幅の本棚に順番にbooksを詰めて行ったら
			// 何段になるのかを確認し、それがmを以下であることを確認する
			shelf_index := 1
			position_in_stage := 0
			for i := 0; i < n; i++ {
				// 入れることができない本がある時点でこのwidthは不採用
				if books[i] > width {
					return false
				}
				// 新たに本を追加することができるかをチェックする
				if position_in_stage + books[i] <= width {
					// 新たに本を入れることができたので、そのステージにおける
					// 現在の本の位置を記録
					position_in_stage += books[i]
				} else {
					// 新たな本を入れることができなかったので、一段下のステージに
					// 入れれば良い
					position_in_stage = books[i]
					shelf_index++ // 本棚のステージ数が増えた
				}
			}
			return shelf_index <= m // 条件を満たすかの確認
		}
		low, high := 0, MAX_WIDTH
		for low < high {
			mid := (low+high)/2
			if check(mid) {
				high = mid
			} else {
				low = mid+1
			}
			// log.Printf("low: %d, high: %d\n", low, high)
		}
		fmt.Println(low)
	}
}

C++: #include<algorithm>
using namespace std;

#define NMAX 100
#define KMAX 100
static const int INFTY = (1<<21);

// n >= k
int compute( int n, int k, int S[NMAX+1] ){
    
    int M[NMAX+1][KMAX+1], D[NMAX+1][KMAX+1];
    int P[NMAX+1];
    
    P[0] = 0;
    for ( int i = 1; i <= n; i++ ) P[i] = P[i-1] + S[i];
    
    for ( int i = 1; i <= n; i++ ) M[i][1] = P[i];
    for ( int j = 1; j <= k; j++ ) M[1][j] = S[1];
    
    for ( int i = 2; i <= n; i++ ){
	for ( int j = 2; j <= k; j++ ){
	    M[i][j] = INFTY;
	    for ( int x = 1; x <= i-1; x++ ){
		int maximum = max( M[x][j-1], P[i] - P[x] );
		if ( M[i][j] > maximum ){
		    M[i][j] = maximum;
		    D[i][j] = x;
		}
	    }
	}
    }
}

int main(){
    int n, k, S[NMAX+1];
    while(1){
	cin >> k >> n;
	if ( k == 0 && n == 0 ) break;
	for ( int i = 1; i <= n; i++ ) cin >> S[i];
	cout << compute(n, k, S) << endl;
    }
    return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>

using namespace std;

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define BW(a,x,b) ((a)<=(x)&&(x)<=(b))
#define F first
#define S second
#define INF 1 << 30

typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef queue<int> qi;
typedef long long ll;

int m, n, book[128], shelf[32];

int dfs(int copy, int step){
  //  fprintf(stderr, "%d %d\n", copy, step);
  if(step == m) return INF;
  if(copy == n){
    int res = 0;
    rep(i, m) res = max(res, shelf[i]);
    return res;
  }

  int res = INF;
  shelf[step] += book[copy];
  res = min(res, dfs(copy+1, step));
  shelf[step] -= book[copy];

  shelf[step+1] = book[copy];
  res = min(res, dfs(copy+1, step+1));
  shelf[step+1] -= book[copy];
  return res;
}

int main(){
  while(scanf("%d%d", &m, &n) && m+n){
    rep(i, n){
      scanf("%d", book+i);
    }
    memset(shelf, 0, sizeof(shelf));
    printf("%d\n", dfs(0, 0));

  }
  return 0;
}

C++: #include <bits/stdc++.h>
using namespace std;

int main() {
  int M, N;
  while(cin >> M >> N && M) {
    vector<int> books(N);
    for(int i=0; i<N; i++) {
      cin >> books[i];
    }
    
    int l = -1, r = 1500000;
    while(r - l > 1) {
      int m = (l+r)/2;
      int bpos = 0;
      for(int i=0; i<M; i++) {
	int size = m;
	for(;;) {
	  if(bpos == N) break;
	  if(size - books[bpos] < 0) break;
	  size -= books[bpos++];
	}
	if(bpos == N) break;
      }
      if(bpos == N) {
	r = m;
      } else l = m+1;
    }
    
    cout << l+1 << endl;
  }
  
  return 0;
}

C++: #include<bits/stdc++.h>
using namespace std;

int m, n;
int data[101];

bool func( int num ) {
  int sum = 0, cnt = 1;
  for(int i=0; i<n; i++) {
    if( sum + data[i] <= num ) {
      sum += data[i];
    } else {
      sum = data[i];
      cnt++;
    }
  }

  if( cnt <= m ) return true;
  else return false;
}


int main() 
{
  while( cin >> m >> n, m+n ) {
    int ma = 0;
    for(int i=0; i<n; i++) {
      cin >> data[i];
      ma = max(ma, data[i]);
    }
    
    int l = 0, r = 1500000;
    int now;
    while( l != r ) {
      now = (l + r) / 2;
      if( now >= ma && func( now ) ) {
	r = now;
      } else {
	l = now+1;
      }
    }
    
    cout << l << endl;
  }
  
}

C++: #include <iostream>
using namespace std;

int m,n,*b,ans;

int max(int *l, int size){
	int tmp = l[0];
	for(int i=1; i<size; i++)
		if(tmp < l[i])
			tmp = l[i];
	return tmp;
}

int min(int *l, int size){
	int tmp = l[0];
	for(int i=0; i<size; i++)
		if(tmp > l[i])
			tmp = l[i];
	return tmp;
}

bool bbb(){
	int j=0;
	int a[m];
	for(int i=0; i<m; i++){
		a[i] = 0;
		for(; j<n; j++){
			a[i] += b[j];
			if(a[i] > ans){
				a[i] -= b[j];
				break;
			}
		}
	}
	if(j == n)
		return true;
	else
		return false;
}

void solve(){
	int plus = min(b, n);
	while(true){
		if(bbb())
			return;
		ans += plus;
	}
}

int main(){
	while(true){
		cin >> m >> n;
		if(!m && !n)
			return 0;
		b = new int[n];
		for(int i=0; i< n; i++)
			cin >> b[i];
		ans = max(b, n);
		solve();
		cout << ans << endl;
		delete[] b;
	}
}

C++: #include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <functional>
#include <numeric>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <utility>
#include <sstream>
#include <complex>

using namespace std;

#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,N) for(long long i=0;i<(N);i++)
#define ALL(s) (s).begin(),(s).end()
#define fi first
#define se second

#define PI acos(-1.0)
#define INF 1000000007
#define EPS 1e-10

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<double, double> PD;
typedef pair<string, ll> PS;
typedef vector<ll> V;
typedef pair<P, char> PC;

ll  n, m, b[1000];

int main(){
	while (cin >> m >> n&&n + m){
		ll MAX = -1;
		REP(i, n){
			cin >> b[i];
			MAX = max(MAX, b[i]);
		}
		if (m >= n){
			cout << MAX << endl;
			continue;
		}
		ll lb = -1, ub = 1500000;
		while (ub - lb > 1){
			int co = 0;
			ll mid = (lb + ub) / 2;
			ll sum = 0;
			REP(i, n){
				sum += b[i];
				if (sum > mid){
					sum = b[i];
					co++;
				}
			}
			if (co < m)ub = mid;
			else lb = mid + 1;
		}
		cout << ub << endl;
	}
}

C++: #include <iostream>
#include<cstdio>
#include <cstring>	// require memset
#include <fstream>	// require freopen

using namespace std;

int m, n;	// {IÌi 1  m  20, {Ìª 1  n  100
int w[100];

bool calc_m (int curr_w )
{
	int cm = 0;
	int j = 0;
	while (j < n ){
		int cw = 0;
		while (cw + w[j] <= curr_w && j < n ){
			cw += w[j];
			j++;
		} // end while
		cm++;
		if (cm == m )
			false;
	} // end if

	return true;
}

int main()
{
//	cut here before submit 
//	freopen ("testcase.persistence", "r", stdin );

	const int MaxW = 1500000;

	for (;; ){// {IÌ ans  1500000
		scanf ("%d%d", &m, &n ); if (!m ) break;
		memset (w, 0, sizeof (w ) );

		for (int i = 0; i < n; i++ ){
			scanf ("%d", w+i );
		} // end for
		int l = w[0];
		int r = MaxW;
		int mid = 0;
		while (l <= r ){
			mid = (l+r)/2;
			if (calc_m (mid ) ){
				r = mid-1;		
			}else{
				l = mid+1;
			} // end if
		} // end while
		cout << mid << endl;
	} // end loop
		
	return 0;
}