2.9万

C14H23ClN2O
no_one

FYQ357
incra

gAg

Txoon
Mhbfy
277

AcWing2AK
ღSupperღ
Cold_heartless

12小时前

### 魔法宝石

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

int n, m;
int f[3010][10010];
int v[3010], w[3010];

int main() {
cin >> n >> m;
for (int i = 1; i <= n; i ++ ) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ ){
f[i][j] = f[i - 1][j];
if (j >= w[i])
f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + v[i]);
}
cout << f[n][m] << endl;
return 0;
}


### Bessie 的体重问题

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

int n, m;
int f[510][45010];
int w[510];

int main() {
cin >> m >> n;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ ){
f[i][j] = f[i - 1][j];
if (j >= w[i])
f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + w[i]);
}
cout << f[n][m] << endl;
return 0;
}


### 干草出售

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

int n, m;
int f[50010];

int main() {
cin >> m >> n;
for (int i = 1; i <= n; i ++ ){
int x;
cin >> x;
for (int j = m; j >= x; j -- )
f[j] = max(f[j], f[j - x] + x);
}

cout << f[m] << endl;
return 0;
}


### Corn Fields

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 13, M = 1 << N, mo = 100000000;

int n, m;
int f[N][M];
int st[N];

bool check(int i, int j){
if ((st[i] & j) != j) return false;
if (j & (j << 1)) return false;
return true;
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i ++ ){
st[i] = 0;
for (int j = 1; j <= m; j ++ ){
int x;
scanf("%d", &x);
st[i] = (st[i] << 1) + x;
}
}
memset(f, 0, sizeof f);
f[0][0] = 1;
for (int i = 1; i <= n; i ++ ){
for (int j = 0; j < 1 << m; j ++ ){
if (!check(i, j)) continue;
for (int k = 0; k < 1 << m; k ++ )
if (!(j & k))
f[i][j] = (f[i][j] % mo + f[i - 1][k] % mo) % mo;
}
}
int ans = 0;
for (int i = 0; i < 1 << m; i ++ )
ans = (ans % mo + f[n][i] % mo) % mo;
printf("%d\n", ans);
return 0;
}


### 单词接龙

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 25;

int n;
string word[N];
int used[N];
int g[N][N], ans;

void dfs(string str, int last){
ans = max(ans, (int)str.size());
used[last] ++ ;
for (int i = 1; i <= n; i ++ )
if (g[last][i] && used[i] < 2)
dfs(str + word[i].substr(g[last][i]), i);
used[last] -- ;
}

int main() {
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> word[i];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ ){
string a = word[i], b = word[j];
for (int k = 1; k < min(a.size(), b.size()); k ++ )
if (a.substr(a.size() - k, k) == b.substr(0, k)){
g[i][j] = k;
break;
}
}
for (int i = 1; i <= n; i ++ )
dfs(word[i], i);
cout << ans << endl;
return 0;
}


### Bugs Integrated, Inc.




### FatMouse and Cheese

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m;
int w[N][N], f[N][N];

int dfs(int x, int y){
if (f[x][y] != -1) return f[x][y];
int mx = 0;
for (int i = 1; i <= m; i ++ )
for (int j = 0; j < 4; j ++ ){
int nx = x + dx[j] * i, ny = y + dy[j] * i;
if (w[nx][ny] > w[x][y] && nx >= 1 && nx <= n && ny >= 1 && ny <= n)
mx = max(mx, dfs(nx, ny));
}
return f[x][y] = mx + w[x][y];
}

int main()
{
while (~scanf("%d%d", &n, &m)){
if (n == -1 && m == -1) break;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
cin >> w[i][j];
memset(f, -1, sizeof f);
printf("%d\n", dfs(1, 1));
}
return 0;
}


### 搬寝室

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 2010;

typedef long long LL;

int n, m;
LL f[N][1100];
LL w[N];

int main()
{
while (~scanf("%d%d", &n, &m)){
for (int i = 1; i <= n; i ++ ) cin >> w[i];
sort(w + 1, w + 1 + n);
memset(f, 0x3f, sizeof f);
for (int i = 0; i <= n; i ++ ) f[i][0] = 0;
for (int i = 2; i <= n; i ++ )
for (int j = 1; 2 * j <= i; j ++ )
f[i][j] = min(f[i - 1][j], f[i - 2][j - 1] + (w[i] - w[i - 1]) * (w[i] - w[i - 1]));
printf("%lld\n", f[n][m]);
}
return 0;
}


### Warcraft

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 110;

int n, t, q;
int v[N], w[N];
int f[N][N], ans;

int main()
{
while (~scanf("%d%d%d", &n, &t, &q)){
if (!n && !t && !q) break;
ans = 0;
for (int i = 1; i <= n; i ++ ) scanf("%d%d", &v[i], &w[i]);
v[0] = 0, w[0] = 1;
memset(f, 0, sizeof f);
int num = 100 / q;
if (100 % q) num ++ ;
for (int k = 1; k <= num; k ++ ){
for (int j = 0; j <= 100; j ++ ){
int next_j = min(100, j + t);
for (int i = 0; i <= n; i ++ ){
if (v[i] + j <= 100)
f[k][next_j] = max(f[k][next_j], f[k - 1][j + v[i]] + w[i]);
}
if (f[k][next_j] >= 100){
ans = k;
break;
}
}
if (ans) break;
}
if (!ans) puts("My god");
else printf("%d\n", ans);
}
return 0;
}


### 踩方格

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 25;

int n;
int s[N], w[N], e[N];

int main()
{
s[1] = w[1] = e[1] = 1;
cin >> n;
for (int i = 2; i <= n; i ++ ){
s[i] = s[i - 1] + w[i - 1] + e[i - 1];
w[i] = s[i - 1] + w[i - 1];
e[i] = s[i - 1] + e[i - 1];
}
cout << s[n] + w[n] + e[n] << endl;
return 0;
}


### 盒子与球

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

int n, m;
int f[N][N], fac[N];

int main()
{
cin >> n >> m;
f[0][0] = fac[0] = 1;
for (int i = 1; i <= m; i ++ ) fac[i] = fac[i - 1] * i;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= min(m, i); j ++ )
f[i][j] = f[i - 1][j - 1] + f[i - 1][j] * j;
cout << f[n][m] * fac[m] << endl;
return 0;
}


### 魔法少女

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10010;

int n;
int f[N][2], w[N];

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> w[i];
f[1][1] = w[1], f[2][1] = w[2];

for (int i = 3; i <= n; i ++ ){
f[i][0] = min(f[i - 1][1], f[i - 2][1]);
f[i][1] = min(f[i - 1][0], f[i - 1][1]) + w[i];
}
cout << min(f[n][0], f[n][1]) << endl;
return 0;
}


### 红牌

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 2010;

int n, m;
int g[N][N];
int f[N][N];

int main()
{
cin >> n >> m;
for (int i = 1; i <= m; i ++ )
for (int j = 1; j <= n; j ++ )
cin >> g[i][j];
for (int i = 1; i <= m; i ++ )
f[1][i] = g[i][1];
for (int i = 2; i <= n; i ++ )
for (int j = 1; j <= m; j ++ ){
if (j > 1) f[i][j] = min(f[i - 1][j], f[i - 1][j - 1]) + g[j][i];
else f[i][j] = min(f[i - 1][j], f[i - 1][m]) + g[j][i];
}
int res = 0x3f3f3f3f;
for (int i = 1; i <= m; i ++ )
res = min(res, f[n][i]);
cout << res << endl;
return 0;
}


### 数的计算

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

int n;
int f[N];

int main()
{
f[0] = f[1] = 1;
for (int i = 2; i <= 1000; i ++ )
for (int j = 0; j <= i / 2; j ++ )
f[i] += f[j];
cin >> n;
cout << f[n] << endl;
return 0;
}


### 相似基因

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
char s1[N], s2[N];
int p1[N], p2[N];
int f[N][N];
int g[6][6] = {
{0},
{0, 5, -1, -2, -1, -3},
{0, -1, 5, -3, -2, -4},
{0, -2, -3, 5, -2, -2},
{0, -1, -2, -2, 5, -1},
{0, -3, -4, -2, -1, 0}
};

int main()
{
cin >> n >> s1 + 1 >> m >> s2 + 1;
for (int i = 1; i <= n; i ++ ){
if (s1[i] == 'A') p1[i] = 1;
if (s1[i] == 'C') p1[i] = 2;
if (s1[i] == 'G') p1[i] = 3;
if (s1[i] == 'T') p1[i] = 4;
}
for (int i = 1; i <= m; i ++ ){
if (s2[i] == 'A') p2[i] = 1;
if (s2[i] == 'C') p2[i] = 2;
if (s2[i] == 'G') p2[i] = 3;
if (s2[i] == 'T') p2[i] = 4;
}
for (int i = 1; i <= n; i ++ )
f[i][0] = f[i - 1][0] + g[p1[i]][5];
for (int i = 1; i <= m; i ++ )
f[0][i] = f[0][i - 1] + g[5][p2[i]];
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
f[i][j] = max(f[i - 1][j - 1] + g[p1[i]][p2[j]], max(f[i - 1][j] + g[p1[i]][5], f[i][j - 1] + g[5][p2[j]]));
cout << f[n][m] << endl;
return 0;
}


### 超级楼梯

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 50;

typedef long long LL;

LL f[N];

int main(){
f[1] = 0;
f[2] = 1;
f[3] = 2;
for (int i = 4; i <= 40; i ++ )
f[i] = f[i - 1] + f[i - 2];
int T;
cin >> T;
while (T -- ){
int x;
cin >> x;
cout << f[x] << endl;
}
return 0;
}


### 路径计数2

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010, mo = 100003;

typedef long long LL;

int f[N][N];
bool st[N][N];
int n, m;

int main() {
cin >> n >> m;
for (int i = 1; i <= m; i ++ ){
int a, b;
cin >> a >> b;
st[a][b] = true;
}
f[1][1] = 1;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ ){
if (!st[i - 1][j])  f[i][j] = (f[i][j] + f[i - 1][j] % mo) % mo;
if (!st[i][j - 1])  f[i][j] = (f[i][j] + f[i][j - 1] % mo) % mo;
}
cout << f[n][n] % mo << endl;

return 0;
}


### AGTC

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;

typedef long long LL;

int n, m;
char a[N], b[N];
int f[N][N];

int main() {
while (cin >> n >> a + 1 >> m >> b + 1){
for (int i = 1; i <= n; i ++ ) f[i][0] = i;
for (int i = 1; i <= m; i ++ ) f[0][i] = i;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ ){
if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1];
else f[i][j] = min(f[i - 1][j - 1] + 1, min(f[i - 1][j] + 1, f[i][j - 1] + 1));
}
cout << f[n][m] << endl;
}

return 0;
}


### Common Subsequence

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 1010;

typedef long long LL;

char s1[N], s2[N];
int f[N][N];

int main(){
while (~scanf("%s%s", s1 + 1, s2 + 1)){
int len1 =  strlen(s1 + 1), len2 = strlen(s2 + 1);
for (int i = 1; i <= len1; i ++ ) f[i][0] = 0;
for (int i = 1; i <= len2; i ++ ) f[0][i] = 0;
for (int i = 1; i <= len1; i ++ )
for (int j = 1; j <= len2; j ++ ){
f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (s1[i] == s2[j])
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
cout << f[len1][len2] << endl;
}

return 0;
}


### 最长公共子序列Lcs

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 1010;

typedef long long LL;

char s1[N], s2[N];
int f[N][N];
char path[N];
int pos = N-1;

int main(){
scanf("%s%s", s1 + 1, s2 + 1);
int len1 =  strlen(s1 + 1), len2 = strlen(s2 + 1);
for (int i = 1; i <= len1; i ++ ) f[i][0] = 0;
for (int i = 1; i <= len2; i ++ ) f[0][i] = 0;
for (int i = 1; i <= len1; i ++ )
for (int j = 1; j <= len2; j ++ ){

f[i][j] = max(f[i - 1][j], f[i][j - 1]);
if (s1[i] == s2[j])
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
while (len1 > 0 && len2 > 0)
{
if (s1[len1] == s2[len2]){
path[pos --] = s1[len1];
len1 -- , len2 -- ;
}else if(f[len1 - 1][len2] > f[len1][len2 - 1]) len1 -- ;
else len2 -- ;
}
printf("%s\n", path + pos + 1);
return 0;
}


#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 1010;

typedef long long LL;

char s1[N], s2[N];
int f[N][N], pre[N][N];

void print(int u, int v) {
if (!u && !v) return;
if (!pre[u][v]) {
print(u - 1, v - 1);
printf("%c", s1[u]);
} else if (pre[u][v] == 1) {
print(u - 1, v);
printf("%c", s1[u]);
} else {
print(u, v - 1);
printf("%c", s2[v]);
}
}

int main() {
while (~scanf("%s%s", s1 + 1, s2 + 1)) {

int len1 =  strlen(s1 + 1), len2 = strlen(s2 + 1);

for (int i = 1; i <= len1; i ++ ) f[i][0] = 0, pre[i][0] = 1;
for (int i = 1; i <= len2; i ++ ) f[0][i] = 0, pre[0][i] = -1;
for (int i = 1; i <= len1; i ++ )
for (int j = 1; j <= len2; j ++ ) {
if (s1[i] == s2[j]) {
f[i][j] = f[i - 1][j - 1] + 1;
pre[i][j] = 0;
} else if (f[i - 1][j] > f[i][j - 1]) {
f[i][j] = f[i - 1][j];
pre[i][j] = 1;
} else {
f[i][j] = f[i][j - 1];
pre[i][j] = -1;
}
}
print(len1, len2);
puts("");
}

return 0;
}


### Super Jumping! Jumping! Jumping!

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1010;

typedef long long LL;

int n;
int a[N];
LL f[N];

int main(){
while (scanf("%d", &n) && n){
memset(a, 0, sizeof a);
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ){
f[i] = a[i];
for (int j = 1; j < i; j ++ )
if (a[j] < a[i])
f[i] = max(f[i], f[j] + a[i]);
}
LL res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);
printf("%lld\n", res);
}
return 0;
}


### 最少拦截系统

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 2010;

int n;
int a[N];
int f[N];

int main(){
while (~scanf("%d", &n)){
memset(a, 0, sizeof a);
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ ) cin >> a[i];
for (int i = 1; i <= n; i ++ ){
f[i] = 1;
for (int j = 1; j < i; j ++ )
if (a[j] < a[i])
f[i] = max(f[i], f[j] + 1);
}
int res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, f[i]);
printf("%d\n", res);
}
return 0;
}


### Monkey and Banana

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;

int n, casei;
int f[N];
struct node{
int l,w,h;
}p[N];

bool cmp(node A, node B){
if (A.l != B.l) return A.l > B.l;
else{
if (A.w != B.w) return A.w > B.w;
else return A.h > B.h;
}
}

int main(){
while (scanf("%d", &n) && n){
memset(p, 0, sizeof p);
memset(f, 0, sizeof f);
int m = 0;
for (int i = 1; i <= n; i ++ ){
int a[3];
scanf("%d%d%d", &a[0], &a[1], &a[2]);
sort(a, a + 3);
p[++ m] = {a[2],a[1],a[0]};
p[++ m] = {a[2],a[0],a[1]};
p[++ m] = {a[1],a[0],a[2]};
}
sort(p + 1, p + 1 + m, cmp);
for (int i = 1; i <= m; i ++ ){
f[i] = p[i].h;
for (int j = 1; j < i; j ++ )
if (p[j].l > p[i].l && p[j].w > p[i].w)
f[i] = max(f[i], f[j] + p[i].h);
}
int res = 0;
for (int i = 1; i <= m; i ++ )
res = max(res, f[i]);
printf("Case %d: maximum height = %d\n", ++ casei, res);
}
return 0;
}


### 饭卡

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 1010;

int n, m;
int f[N][N];
int w[N];

int main(){
while (cin >> n && n){
for (int i = 1; i <= n; i ++ ) cin >> w[i];
cin >> m;
if (m < 5){
cout << m << endl;
continue;
}
sort(w + 1, w + 1 + n);
int maxw = w[n];
memset(f, 0, sizeof f);
m -= 5;
for (int i = 1; i < n; i ++ )
for (int j = 0; j <= m; j ++ ){
f[i][j] = f[i - 1][j];
if (j >= w[i])
f[i][j] = max(f[i][j], f[i - 1][j - w[i]] + w[i]);
}
cout << m + 5 - maxw - f[n - 1][m] << endl;
}
return 0;
}


### 数塔

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 110;

int n;
int f[N][N];

int main(){
int T;
cin >> T;
while (T -- ){
cin >> n;
memset(f, 0, sizeof f);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= i; j ++ )
cin >> f[i][j];
for (int i = n - 1; i >= 1; i -- )
for (int j = 1; j <= i; j ++ )
f[i][j] += max(f[i + 1][j], f[i + 1][j + 1]);
cout << f[1][1] << endl;
}
return 0;
}


### 免费馅饼

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 1e5 + 10;

int n;
int w[11][N], f[11][N];

int main(){
while (scanf("%d", &n) && n){
memset(w, 0, sizeof w);
memset(f, 0, sizeof f);
int maxt = 0;
for (int i = 1; i <= n; i ++ ){
int x, t;
scanf("%d%d", &x, &t);
maxt = max(maxt, t);
w[x][t] ++ ;
}
for (int i = 4; i <= 6; i ++ )
f[i][1] = w[i][1];
for (int j = 2; j <= maxt; j ++ )
for (int i = 0; i <= 10; i ++ ){
if (abs(5 - i) > j) f[i][j] = 0;
else{
int x = w[i][j];
if (!i) f[i][j] = max(f[i][j - 1], f[i + 1][j - 1]) + x;
else if (i == 10) f[i][j] = max(f[i][j - 1], f[i - 1][j - 1]) + x;
else f[i][j] = max(f[i][j - 1], max(f[i - 1][j - 1], f[i + 1][j - 1])) + x;
}
}
int ans = 0;
for (int i = 0; i <= 10; i ++ )
for (int j = 1; j <= maxt; j ++ )
ans = max(ans, f[i][j]);
cout << ans << endl;
}
return 0;
}


#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;

int n;
int f[N][12];

int main(){
while (scanf("%d", &n) && n){
memset(f, 0, sizeof f);
int maxt = 0;
for (int i = 1; i <= n; i ++ ){
int x, t;
scanf("%d%d", &x, &t);
maxt = max(maxt, t);
f[t][x] ++ ;
}
for (int i = maxt - 1; i >= 0; i -- )
for (int j = 0; j <= 10; j ++ ){
int x = max(f[i + 1][j], f[i + 1][j + 1]);
if (j > 0) x = max(x, f[i + 1][j - 1]);
f[i][j] += x;
}
printf("%d\n", f[0][5]);
}
return 0;
}


10天前

### 搬书

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 5010;

int n;
int f[N];

int main(){
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> f[i];
for (int i = 2; i <= n; i ++ )
for (int j = 1; j < i; j ++ )
f[i] = min(f[i], f[j] + f[i - j]);
cout << f[n] << endl;
return 0;
}


### 文科生的悲哀

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 10010, mo = 19260817;

int n;
int f[N][4];

int main(){
cin >> n;
f[1][0] = 1;
for (int i = 1; i <= n; i ++ )
for (int j = 0; j < 4; j ++ )
if (f[i][j]){
if (!j)
f[i + 1][1] = (f[i + 1][1] % mo + f[i][j] % mo) % mo;
else if (j == 1){
f[i + 1][0] = (f[i + 1][0] % mo + f[i][j] % mo) % mo;
f[i + 1][2] = (f[i + 1][2] % mo + f[i][j] % mo) % mo;
}
else if (j == 2){
f[i + 1][1] = (f[i + 1][1] % mo + f[i][j] % mo) % mo;
f[i + 1][3] = (f[i + 1][3] % mo + f[i][j] % mo) % mo;
}
else f[i + 1][2] = (f[i + 1][2] % mo + f[i][j] % mo) % mo;
}
int res = 0;
for (int i = 0; i < 4; i ++ )
res += f[n][i] % mo;
cout << res % mo << endl;

return 0;
}


### 乘积最大

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 45;

int n, m;
int f[N][10];
int w[N][N];
char str[N];

int main(){
cin >> n >> m;
cin >> str + 1;
for (int i = 1; i <= n; i ++ ) w[i][i] = str[i] - '0';
for (int i = 1; i < n; i ++ )
for (int j = i + 1; j <= n; j ++ )
w[i][j] = w[i][j - 1] * 10 + w[j][j];
for (int i = 1; i <= n; i ++ ) f[i][0] = w[1][i];
for (int i = 2; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
for (int k = 1; k < i; k ++ )
f[i][j] = max(f[i][j], f[k][j - 1] * w[k + 1][i]);
cout << f[n][m] << endl;
return 0;
}


dfs

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>

using namespace std;

const int N = 10;

int n, m;
string str;
int p[N];
int res;

int get(int l, int r){
int res = 0;
for (int i = l; i <= r; i ++ ) res = res * 10 + (str[i] - '0');
return res;
}

void dfs(int u, int v){
if (u > m){
int ans = 1;
for (int i = 0; i <= m; i ++ ) ans *= get(p[i] + 1, p[i + 1]);
res = max(res, ans);
return;
}
for (int i = v; i < n; i ++ ){
p[u] = i;
dfs(u + 1, i + 1);
}
}

int main(){
cin >> n >> m;
cin >> str;
p[0] = -1, p[m + 1] = n - 1;
dfs(1, 0);
cout << res << endl;
return 0;
}