Submission #998718

---

Source Code Expand

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <climits>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

#define DIV 1000000007

using namespace std;

long long K;
long long maxilen;
long long minilen;
string S;

map<pair<int, int>, long> memo;


long dfs(int pos, int maxinum, int mininum){
	//cout << "mininum = " << mininum << " maxinum " << maxinum << " pos = " << pos << endl;
	if(maxinum == 0 && mininum == 0){
		return 0;
	}
	if(memo.count(make_pair(maxinum, mininum)) != 0){
		return memo[make_pair(maxinum, mininum)];
	}

	//choose maxi
	long f = -1;
	long s = -1;
	if(maxinum > 0){
		f = max(f, dfs(pos + maxilen, maxinum - 1, mininum));
		//cout << "mininum = " << mininum << " maxinum " << maxinum << " pos = " << pos << " maxi " << atol(S.substr(pos, maxilen).c_str()) << endl;
		f = max(f, atol(S.substr(pos, maxilen).c_str()));
	}
	//choose mini
	if(mininum > 0){
		s = max(s, dfs(pos + minilen, maxinum, mininum - 1));
		s = max(s, atol(S.substr(pos, minilen).c_str()));
		//cout << "mininum = " << mininum << " maxinum " << maxinum << " pos = " << pos << " mini " << atol(S.substr(pos, minilen).c_str())<< endl;
	}
	if(s == -1){
		memo[make_pair(maxinum, mininum)] = f;
		return f;
	}
	if(f == -1){
		memo[make_pair(maxinum, mininum)] = s;
		return s;
	}
	memo[make_pair(maxinum, mininum)] = min(f, s);
	return min(f, s);
}


int main(){
	cin >> K >> S;
	long long Slen = S.size();
	long long maxinum;
	long long mininum;
	if(Slen%(K+1) == 0){
		maxilen = Slen/(K+1);
		minilen = maxilen-1;
		for(int i = 0; i <= K+1; i++){
			if(maxilen * i + minilen * (K+1-i) == Slen){
				maxinum = i;
				mininum = K+1-i;
				break;
			}

		}
	}else{
		maxilen = Slen/(K+1) + 1;
		minilen = maxilen-1;
		for(int i = 0; i <= K+1; i++){
			if(maxilen * i + minilen * (K+1-i) == Slen){
				maxinum = i;
				mininum = K+1-i;
				break;
			}

		}
	}
	//cout << "maxinum " << maxinum << endl;
	//cout << "mininum " << mininum << endl;
	cout << dfs(0, maxinum, mininum) << endl;;

	//dfs(0, 

}

Submission Info

Judge Result