Submission #486832

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cstdio>
#include <cstring>
#include <cmath>

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

typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> P;
typedef std::pair<P, int> PP;
struct edge{ int to, time, cost; };
const double esp = 1e-9;
const int inf = (int)1e+9;

int d, n;
std::string w[10005];
std::string dp[205];
std::map<char, char> map;
int mode;

void init(){
	map['O'] = '0';
	map['D'] = '0';
	map['I'] = '1';
	map['Z'] = '2';
	map['E'] = '3';
	map['h'] = '4';
	map['s'] = '5';
	map['q'] = '6';
	map['L'] = '7';
	map['B'] = '8';
	map['G'] = '9';
}

std::string smax(std::string lhs, std::string rhs){
	if (mode == 0)return std::max(lhs, rhs);
	else if (mode == 1){
		if (lhs.size() == rhs.size())return std::max(lhs, rhs);
		return (lhs.size() > rhs.size() ? lhs : rhs);
	}
}

int main(){
	init();
	std::cin >> d >> n;
	std::string s = "0";
	rep(i, n){
		std::cin >> w[i];
		rep(j, w[i].size())w[i][j] = map[w[i][j]];
		std::reverse(w[i].begin(), w[i].end());
		s = std::max(s, w[i]);
	}
	rep(i, s.size()){
		if (s[i] != '0'){
			mode = 1;
			break;
		}
		if (i == s.size() - 1)mode = 2;
	}
	if (mode == 1 && s[0] == '0')mode = 0;
	if (mode == 2){
		std::cout << "0" << std::endl;
		return 0;
	}
	std::sort(w, w + n, [](const std::string &a, const std::string &b){return a + b > b + a; });

	rep(i, d + 1)dp[i] = "0";
	dp[0] = "";
	rep(i, n){
		for (int j = d; j >= 0; --j){
			if (dp[j] == "0")continue;
			int s = j + w[i].size();
			if (s <= d)dp[s] = smax(dp[s], dp[j] + w[i]);
		}
	}
	std::string ans = "0";
	rep(i, d + 1)ans = smax(ans, dp[i]);

	if (mode == 0){
		ans.insert(1, ".");
		while (ans[ans.size() - 1] == '0')ans.erase(ans.size() - 1);
	}
	std::cout << ans << std::endl;
	return 0;
}

Submission Info

Judge Result