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 <complex>
#include <sstream>
#include <string>
#include <algorithm>
#include <deque>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <vector>
#include <set>
#include <limits>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <ctime>
using namespace std;
#define REP(i, j) for(int i = 0; i < (int)(j); ++i)
#define FOR(i, j, k) for(int i = (int)(j); i < (int)(k); ++i)
#define SORT(v) sort((v).begin(), (v).end())
#define REVERSE(v) reverse((v).begin(), (v).end())
typedef pair<int, int> P;
const int INF = 1e9;

class C{
  public:
    int n, w, m;
    C(){}
    C(int _n, int _w, int _m){ n = _n; w = _w; m = _m; }
    bool operator > (const C &c) const {
      if(w != c.w) return w > c.w;
      return m < c.m;
    }
};

int main() {
  int M, N;
  while(cin >>M >>N && M){
    vector<int> v(N + 1); FOR(i, 1, N + 1) cin >>v[i];
    FOR(i, 1, v.size()) v[i] += v[i - 1];
    priority_queue<C, vector<C>, greater<C> > open;
    open.push(C(1, 0, 0)); 
    vector< vector<int> > closed(N + 1, vector<int>(M + 1, INF));
    closed[1][0] = 0;
    while(!open.empty()){
      C tmp = open.top(); open.pop();
      int n = tmp.n, w = tmp.w, m = tmp.m;
      //cout <<"n = " <<n <<", w = " <<w <<", m = " <<m <<endl;
      if(m == M){ cout <<w <<endl; break; }
      if(n == N && m == M){ cout <<w <<endl; break; }
      if(m + 1 == M){
        int nw = v[N] - v[n - 1];
        if(closed[N][m + 1] <= nw) open.push(C(N, max(w, nw), m + 1));
        open.push(C(N, max(w, nw), m + 1));
        continue;
      }
      FOR(next, n, N + 1){
        int nw = v[next] - v[n - 1];
        //cout <<"    " <<next + 1 <<", " <<max(w, nw) <<", " <<m + 1 <<" | " <<closed[next][m + 1] <<", " <<max(w, nw) <<endl;
        if(closed[next][m + 1] <= max(w, nw)) continue;
        //cout <<"    " <<"!" <<endl;
        closed[next][m + 1] = nw;
        open.push(C(next + 1, max(w, nw), m + 1));
      }
    }
  }
  return 0;
}

C++: #include<stdio.h>

int m,n;
int x[100];

int lower( int INF,int (*compare)(int) )
{
	int start = 0,end = INF,medi;
	while( start <= end )
	{
		medi = (start+end)/2;
		if( compare(medi) ){
			if( compare(medi-1) )
				end = medi-1;
			else
				break;
		}
		else{
			start = medi+1;
		}
	}
	return medi;
}

int compare( int size ){	//size:本棚の幅
	int i,cnt = 0;
	int rui = 0;
	
	for( i = 0;i < n;i++ ){
		if( size < x[i] )
			return 0;
		if( rui+x[i] > size ){
			rui = x[i];
			cnt++;
		}
		else{
			rui += x[i];
		}
	}
	if( cnt >= m )
		return 0;
	return 1;
}

int main(){
	while( scanf("%d%d",&m,&n) ){
		if( m == 0 )
			break;
		
		for( int i = 0;i < n;i++ ){
			scanf("%d",x+i);
		}
		printf("%d\n",lower( 1500000,compare ) );
	}
	return 0;
}

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



int n,m;
vector<int> cost;
vector<vector<int> > dp;
void init(){
  cost.clear();
  dp.clear();
}

bool input(){
  cin>>m>>n;
  if(n==0&&m==0)return 0;
  for(int i=0;i<n;i++){
    int tmp;
    cin>>tmp;
    cost.push_back(tmp);
  }
  return 1;
}

int rec(int i,int x){
  if(i==n){
    return 0;
  }
  if(x==m){
    return INT_MAX-1500010;
  }
  if(dp[i][x]!=0){
    return dp[i][x];
  }
  dp[i][x]=INT_MAX-1500010;
  int c=cost[i];
  for(int j=i+1;j<cost.size()+1;j++){
    dp[i][x]=min(dp[i][x],max(rec(j,x+1),c));
    c+=cost[j];
  }
  return dp[i][x];
}


int solve(){
  dp.resize(n);
  for(int i=0;i<n;i++){
    dp[i].resize(m);
  }
  return rec(0,0);
}


int main(){
  while(init(),input()){
    cout<<solve()<<endl;
  }
}

C++: #include <iostream>
#include <cstring>

using namespace std;

#define BOOK_NUM_MAX 100
#define SHELF_NUM_MAX 20

int book_thick[BOOK_NUM_MAX] = {0};
int dp_table[SHELF_NUM_MAX][BOOK_NUM_MAX] = {-1};

int solve(int m, int n){
	int sum, val, min, tmp;
	
	if(dp_table[m][n] == -1){
		if(m == 1){
			sum = 0;
			for(int i=1; i <= n;++i){
				sum += book_thick[n - i];
			}
			val = sum;
		}else if(n == 0){
			val = 0;
		}else{
			sum = 0;
			min = solve(m-1, n);
			for(int i=1; i <= n;++i){
				sum += book_thick[n - i];
				tmp = solve(m-1,n-i);
				tmp = sum > tmp ? sum : tmp;
				min = min > tmp ? tmp : min; 
			}
			val = min;
		}
		dp_table[m][n] = val;
	}else{
		val = dp_table[m][n];
	}
	return val;
}

int main() {
	
	int m, n;
	int i,j;
	
	while(cin >> m >> n, m!= 0 && n!= 0){
		for(i=0;i<n;++i){
			cin >> book_thick[i];
		}
		memset(dp_table    , -1, sizeof(dp_table));

		cout << solve(m,n) << endl;
	}
	
	return 0;
}

C++: #include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,n) FOR(i,0,n)

int n, m;
int v[100];

bool check(int x) {
	int cnt = 0, pos = 0;
	while (pos < n) {
		cnt++;
		int now = v[pos++];
		while (pos < n && now + v[pos] <= x) now += v[pos++];
	}
	
	return cnt <= m;
}

int main() {
	while (cin >> m >> n, n || m) {
		REP(i, n) scanf("%d", &v[i]);
		
		int r = 1500001, l = -1;
		
		while (r - l > 1) {
			int mid = (r + l) / 2;
			if (check(mid)) r = mid;
			else l = mid;
		}
		
		cout << r << endl;
	}
	
	return 0;
}

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

int main()
{
	int M,N;
	while(scanf("%d%d", &M,&N), (M||N))
	{
		int wid[100]={0}, swid[100]={0};
		swid[0]=0;
		for(int i=0; i<N; i++)
		{
			scanf("%d", &wid[i]);
			if(i==0) swid[i]=wid[i];
			else swid[i]=swid[i-1]+wid[i];
		}
		
		int hi=N, lo=0,mi;
		
		while(hi>lo)
		{
			mi=(hi+lo)/2;
			int cap=0, d=1;
			bool g=true;
			for(int i=0; i<N; i++)
			{
				if(swid[mi] < wid[i])
				{
					g=false;
					break;
				}
				if(cap+wid[i] > swid[mi])
				{
					cap=wid[i];
					d++;
				}
				else
				{
					cap+=wid[i];
				}
			}
			
			if(!g||d>M) lo=mi+1;
			else hi=mi;
		}
		
		printf("%d\n", swid[mi]);
	}
}

C++: #include<cstdio>
#include<algorithm>
using namespace std;
int main(){
  int m,n,w[101],l,r,mid,cnt,dan;
  while(scanf("%d %d",&m,&n),m!=0||n!=0){
    l = 0;
    r = 0;
    for(int i=0;i<n;i++){
      scanf("%d",&w[i]);
      l = max(l,w[i]);
      r += w[i];
    }
    while(l < r){
      mid = (l+r-1)/2;
      cnt = 0;
      dan = 1;
      for(int i=0;i<n;i++){
	if(cnt+w[i] > mid){
	  cnt = 0;
	  dan++;
	}
	cnt += w[i];
      }
      
      if(dan > m) l = mid+1;
      else r = mid;
      
    }
    printf("%d\n",mid);
  }
  return(0);
}