Language: C++

#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


typedef pair<int,int> P;
#define NUM 4001

struct Edge{
	Edge(int arg_to,int arg_rank){
		to = arg_to;
		rank = arg_rank;
	}
	bool operator<(const struct Edge &arg) const{
		return rank < arg.rank;
	}
	int to,rank;
};

struct Info{
	void set(int arg_loc,int arg_left_div_num){
		loc = arg_loc;
		left_div_num = arg_left_div_num;
	}
	int loc,left_div_num;
};

int N;
int min_rank[NUM][NUM]; //ある場所までの分割数が同じなら、到達エッジのrankは小さいほど良い
vector<int> IN_RANK[NUM];
Info pre[NUM][NUM];
ll table[NUM];
map<ll,int> RANK; //重みの順位
short MAX_DIVIDE[NUM][NUM]; //dp[場所][ある場所に到達するエッジ集合の中でのrank] = 到達までの最大分割数
vector<Edge> G[NUM];


int main(){

	scanf("%d",&N);

	table[0] = 0;

	for(int i = 1; i <= N; i++){
		scanf("%lld",&table[i]);
		table[i] += table[i-1];
	}

	vector<ll> V;
	V.push_back(-HUGE_NUM);

	//エッジのrankを求める
	for(int left = 0; left <= N-1; left++){
		for(int right = left+1; right <= N; right++){
			V.push_back(table[right]-table[left]);
		}
	}

	sort(V.begin(),V.end());
	V.erase(unique(V.begin(),V.end()),V.end());

	for(int i = 0; i < V.size(); i++){
		RANK[V[i]] = i;
	}

	//各場所からエッジを張る
	for(int left = 0; left <= N-1; left++){
		for(int right = left+1; right <= N; right++){
			G[left].push_back(Edge(right,RANK[table[right]-table[left]]));
			IN_RANK[right].push_back(RANK[table[right]-table[left]]);
		}
		sort(G[left].begin(),G[left].end());
	}

	//min_rank[到達場所][到達場所より左の分割数] = エッジの最小ランク
	for(int i = 0; i <= N; i++){
		for(int k = 0; k <= i; k++)min_rank[i][k] = BIG_NUM;
	}

	min_rank[0][0] = 0;
	for(int loc = 1; loc <= N; loc++){
		sort(IN_RANK[loc].begin(),IN_RANK[loc].end());
		IN_RANK[loc].erase(unique(IN_RANK[loc].begin(),IN_RANK[loc].end()),IN_RANK[loc].end());
	}

	int L,R,mid;
	int base_rank,start_index,next_loc,next_rank,in_rank;

	//MAX_DIVIDE[場所][相対入次rank] = 左の最大分割数
	for(int loc = 0; loc <= N; loc++){
		for(int in_rank = 0; in_rank <= loc; in_rank++){
			MAX_DIVIDE[loc][in_rank] = -1;
		}
	}

	/*
	 *
	 * ある場所での、左の分割数が等しいなら、到達ランクは小さい方が良い
	 * →ある場所への到達ランクが同じなら、左の分割数が多い方が良いので、
	 *  仮にあるランク(B)が、ある分割数(A)における最小到達ランクであっても、
	 *  AがBにおける最大でないならばSKIPする
	 *
	 */

	IN_RANK[0].push_back(0);
	MAX_DIVIDE[0][0] = 0;

	for(int loc = 0; loc <= N-1; loc++){
		for(int left_div_num = 0; left_div_num <= loc; left_div_num++){
			if(min_rank[loc][left_div_num] == BIG_NUM)continue;

			base_rank = min_rank[loc][left_div_num];

			//base_rankの入次相対rankを求める
			L = 0,R = IN_RANK[loc].size()-1,mid = (L+R)/2;

			while(L <= R){

				if(IN_RANK[loc][mid] == base_rank){
					in_rank = mid;
					break;
				}else if(IN_RANK[loc][mid] > base_rank){
					R = mid-1;
				}else{
					L = mid+1;
				}
				mid = (L+R)/2;
			}

			if(MAX_DIVIDE[loc][in_rank] > left_div_num)continue;

			//エッジの走査始点を求める
			L = 0,R = G[loc].size()-1,mid = (L+R)/2;
			start_index = G[loc].size();

			while(L <= R){
				if(G[loc][mid].rank > base_rank){
					start_index = mid;
					R = mid-1;
				}else{
					L = mid+1;
				}
				mid = (L+R)/2;
			}

			//★★仮にstart_index

			for(int i = start_index; i < G[loc].size(); i++){
				next_loc = G[loc][i].to;
				next_rank = G[loc][i].rank;

				if(min_rank[next_loc][left_div_num+1] > next_rank){

					min_rank[next_loc][left_div_num+1] = next_rank;
					pre[next_loc][left_div_num+1].set(loc,left_div_num);

					//MAX_DIVIDEテーブルを更新する
					L = 0,R = IN_RANK[next_loc].size(),mid = (L+R)/2;

					while(L <= R){

						if(IN_RANK[next_loc][mid] == next_rank){
							in_rank = mid;
							break;
						}else if(IN_RANK[next_loc][mid] > next_rank){
							R = mid-1;
						}else{
							L = mid+1;
						}
						mid = (L+R)/2;
					}

					MAX_DIVIDE[next_loc][in_rank] = max(MAX_DIVIDE[next_loc][in_rank],left_div_num+1);
				}
			}
		}
	}

	int ans_div_num = -1;

	for(int i = N; i >= 1; i--){
		if(min_rank[N][i] != BIG_NUM){
			ans_div_num = i;
			break;
		}
	}

	if(ans_div_num == 1){
		printf("1\n\n");
		return 0;
	}

	stack<int> S;

	int tmp_loc = N,tmp_div_num = ans_div_num;
	Info info;

	while(tmp_loc > 1){
		S.push(pre[tmp_loc][tmp_div_num].loc);
		info = pre[tmp_loc][tmp_div_num];
		tmp_loc = info.loc;
		tmp_div_num = info.left_div_num;
	}

	printf("%d\n",ans_div_num);

	if(!S.empty()){
		printf("%d",S.top());
		S.pop();

		while(!S.empty()){
			printf(" %d",S.top());
			S.pop();
		}
	}
	printf("\n");

	return 0;
}



Compiler output:
a.cc: In function 'int main()':
a.cc:178:76: error: no matching function for call to 'max(short int&, int)'
  178 |                                         MAX_DIVIDE[next_loc][in_rank] = max(MAX_DIVIDE[next_loc][in_rank],left_div_num+1);
      |                                                                         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:178:76: note:   deduced conflicting types for parameter 'const _Tp' ('short int' and 'int')
  178 |                                         MAX_DIVIDE[next_loc][in_rank] = max(MAX_DIVIDE[next_loc][in_rank],left_div_num+1);
      |                                                                         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:178:76: note:   mismatched types 'std::initializer_list<_Tp>' and 'short int'
  178 |                                         MAX_DIVIDE[next_loc][in_rank] = max(MAX_DIVIDE[next_loc][in_rank],left_div_num+1);
      |                                                                         ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~