TLE on #30(本人已疯)
# include <bits/stdc++.h>
# define int long long
# define endl '\n'
# define str string
# define fst ios::sync_with_stdio (0); cin.tie (0); cout.tie (0);
using namespace std;
const int N = 1e6 + 5, M = 2e6 + 5;
const int P = 1e9 + 7;
const int INF = 0x3f3f3f3f3f3f3f3f;
int n;
int a[100];
int sum;
int vis[100];
int len;
int Count;
bool cmp (int x, int y) {
return x > y;
}
bool dfs (int cnt, int nowlen, int pos) { // genshu, xianzaichangdu, weizhi(jieshangyige)
if (cnt == Count) {
return 1;
}
if (nowlen == len) {
return dfs (cnt + 1, 0, 0);
}
int cant = 0;
for (int i = pos; i <= n; i ++ ) {
if ((! vis[i]) && ((nowlen + a[i]) <= len) && (a[i] != cant)) {
vis[i] = 1;
if (dfs (cnt, nowlen + a[i], i + 1)) {
return 1;
}
vis[i] = 0;
cant = a[i];
if (((nowlen + a[i]) == len) || (! nowlen)) {
return 0;
}
}
}
return 0;
}
signed main () {
fst;
cin >> n;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i];
sum += a[i];
}
sort (a + 1, a + 1 + n, cmp);
for ( len = a[1]; len <= sum; len ++ ) {
if (sum % len) {
continue;
}
Count = (sum / len);
memset (vis, 0, sizeof (vis));
if (dfs (0, 0, 1)) {
cout << len;
return 0;
}
}
return 0;
}