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 <iostream>
#include <vector>
#include <algorithm>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

vector<int> v;

bool Check(int x,int n,int m)
{
	int i = 0,j = 0,l = 0;

	while(i < m && j < n)
	{
		if(l + v[i] <= x)
		{
			l += v[i];
			i++;
		}
		else
		{
			l = 0;
			j++;
		}
	}

	if(i == m && j < n) return true;
	else return false;
}

int main()
{
	int n,m;
	while(cin >> n >> m)
	{
		if(n == 0 && m == 0) break;
		
		v.clear();

		rep(i,m)
		{
			int temp;
			cin >> temp;
			v.push_back(temp);
		}

		int l = 0,r = 1500000;

		rep(i,1000)
		{
			int mid = (l + r) / 2;
			if(Check(mid,n,m)) 
			{
				r = mid;
			}
			else 
			{
				l = mid;
			}
		}	

		cout << r << endl;
	}
	return 0;
}

C++: #include <iostream>
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
using namespace std;
bool ok(int m, int n, int s[100], int width) {
	int cnt = 0, size = s[0];
	rep2(i,1,n) {
		if(width<size) return false;
		if(width<size+s[i]) {
			size = 0;
			cnt++;
		}
		size += s[i];
	}
	if(size>0)cnt++;
	if(m>=cnt) return true;
	return false;
}
int main(){
	int m, n;
	while(cin >> m >> n, (m||n)) {
		int s[100] = {};
		rep(i,n) {
			cin >> s[i];
		}
		int lo = 0, hi = 1500000;
		while(hi-lo>=1) {
			int mid = (hi+lo)/2;
			if(ok(m,n,s,mid)) hi = mid;
			else lo = mid+1;
		}
		cout << hi << endl;
	}
	return 0;
}

C++: #include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <sstream>
#include <climits>
#include <cfloat>
#include <complex>

using namespace std;

int main()
{
	int n, m;
	while (scanf("%d %d", &m, &n), n)
	{
		int thick[100];
		for (int i = 0; i < n; ++i)
			scanf("%d", thick+i);

		int maxThick = 0;
		for (int i = 0; i < n; ++i)
			maxThick = max(maxThick, thick[i]);

		int l, r;
		l = maxThick;
		r = 1500000;
		while (l < r)
		{
			int t = (l + r) / 2;

			int step = 0;
			int sum = 0;
			int i;
			for (i = 0; i < n && step < m; ++i)
			{
				if (sum + thick[i] > t)
				{
					sum = 0;
					++step;
				}
				sum += thick[i];
			}
			bool ok = i == n && step < m;
			if (ok)
				r = t;
			else
				l = t + 1;
		}
		printf("%d\n", l);
	}

	return 0;
}

C++: #include <bits/stdc++.h>

using namespace std;

typedef unsigned long long ull;

#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)

int main(){
    int n, m;
    while(cin >> n >> m, n+m){
        vector<int> v(m);
        int mb = 0;
        rep(i, m){ cin >> v[i]; mb = max(mb, v[i]);}
        int lb = -1, ub = 1500010;
        while(ub-lb > 1){
            int mid = (ub+lb)/2;
            int count = 1, width = 0;
            rep(i, m){
                width += v[i];
                if(mid < width){width = v[i]; count++;}
            }
            if(count <= n && mb <= mid){
                ub = mid;
            } else {
                lb = mid;
            }
        }
        cout << ub << endl;
    }
}

C++: #include <iostream>

using namespace std;

typedef unsigned long long ull;

int m, n;
ull w[100];

bool b(ull W)
{
	int need = 1;
	ull s = 0;
	for(int i=0; i<n; i++)
	{
		if(w[i] > W) return false;
		if(s+w[i]>W)
		{
			need++;
			s = 0;
		}
		s+=w[i];
	}
	return need <= m;
}

int main()
{
	while( 1 )
	{
		scanf("%d", &m);
		scanf("%d", &n);
		if((m|n)==0) break;
		
		for(int i=0; i<n; i++) scanf("%llu", &w[i]);
		
		ull l = 1;
		ull r = 150000;
		while(r-l > 1)
		{
			ull mid = (r + l) / 2;
			if(b(mid)) r = mid;
			else l = mid;
		}

		printf("%llu\n", b(l)?l:r);
	}
}

C++: #include<iostream>
using namespace std;
int main(){
  int m,n;
  while(cin >> m >> n){
    if(m==0&&n==0) break;
    int index[n];
    int max = 1500000;
    int min = 0;
    for(int i=0;i<n;i++){
      cin >>  index[i];
      min = index[i] > min ? index[i] : min;
    }
    int tyuou = 0;
    while(min!=max){
      tyuou = (max + min) / 2;
      int sum = 0;
      int count = 1;
      for(int i=0;i<n;i++){
        if(sum+index[i]>tyuou){
          count++;
          sum = index[i];
        } else {
          sum += index[i];
        }
      }
      if(count>m){
        min = tyuou + 1;
      } else {
        max = tyuou;
      }
    }
    cout << max << endl;
  }
}

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

long long int a[150];
int n, m;

bool i_can(int wid, int m){
	int k = 1, sum = 0;
	for(int i = 0;i<=n;i++){
		sum += a[i];
		if(sum > wid){
			sum = a[i];
			k++;
		}
		if (m < k) return false;
	}
	return true;
}

int nibun(int s, int e, int m){
	if(!(i_can((s+e)/2,m))){
		return nibun((s + e) / 2 + 1, e, m);
	}
	else if (s == e) return s;
	else return nibun(s, (s + e) / 2, m);
}

int main(){
	while(cin >> m >> n){
		if (!n && !m) break;
		a[0] = 0;
		for(int i = 1;i<=n;i++){
			cin >> a[i];
		}
		cout << nibun(0, 1500001, m) << endl;
	}
	return 0;
}

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

const int INF = 1 << 30;

int dp[100][20];

int solve(int s, int p, const int m, const vector<int>& books)
{
  if (s >= books.size())
    return 0;

  if (p >= m) {
    int sum = 0;
    for (int i = s; i < books.size(); ++i)
      sum += books[i];
    return sum;
  }

  if (dp[s][p] != -1)
    return dp[s][p];

  int res = INF, sum = 0;
  for (int i = s; i < books.size(); ++i) {
    sum += books[i];
    res = min(res, max(sum, solve(i+1, p+1, m, books)));
  }
  return dp[s][p] = res;
}

int main()
{
  int n, m;
  while (cin >> m >> n) {
    if ((n|m) == 0)
      break;

    vector<int> books(n);
    for (int i = 0; i < n; ++i)
      cin >> books[i];

    memset(dp, -1, sizeof(dp));
    cout << solve(0, 0, m-1, books) << endl;
  }
  return 0;
}

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

int main(){
    while(1){
        int m, n;
        cin >> m >> n;

        if(m + n == 0)  break;

        int w[n], minp = 1000001;
        for(int i = 0; i < n; i++){
            cin >> w[i];
            minp = min(minp, w[i]); 
        }

        int l = minp, r = 1500000;

        while(r-l > 0){
            int mid = (r+l) / 2;

            int tmpm = 1, nowp = 0;
            for(int i = 0; i < n; i++){
                if(nowp + w[i] <= mid){
                    nowp += w[i];
                }else{
                    nowp = w[i];
                    tmpm++;
                }
            }

            if(tmpm <= m)   r = mid;
            else            l = mid+1;
        }

        cout << l << endl;
    }

    return 0;
}