C++(g++ 7.5.0) 解法, 执行用时: 60ms, 内存消耗: 1384K, 提交时间: 2022-09-24 10:05:57

#include <bits/stdc++.h>

using namespace std;

const int maxn = 110;
int a[maxn];
const int N = 1000000;
bool f[N + 100];

int main() {
	int n;
	scanf("%d", &n);
	int g = 0;
	for(int i = 1; i <= n; i++) {
		scanf("%d", a + i);
		g = __gcd(g, a[i]);
	}
	
	if(g != 1) {
		printf("%d\n", -2);
		return 0;
	}
	
	f[0] = 1;
	for(int i = 1; i <= n; i++) {
		for(int j = a[i]; j <= N; j ++) {
			f[j] |= f[j - a[i]];
		}
	}
	
	for(int i = N; i >= 1; i--) {
		if(!f[i]) {
			printf("%d\n", i);
			return 0;
		}
	}
	printf("-1\n");
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 5ms, 内存消耗: 436K, 提交时间: 2022-12-03 18:44:14

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=20005;
bool f[N];
int main(){
	f[0]=true;
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&x);
		for(int j=0;j+x<=20000;j++)
		f[j+x]|=f[j];
	}
	int ans=-1;
	for(int i=20000;i>=0;i--)
	if(!f[i])
	{
		ans=i;
		break;
	}
	printf("%d",ans>10000?-2:ans);
	return 0;
}

pypy3 解法, 执行用时: 154ms, 内存消耗: 30176K, 提交时间: 2022-09-24 10:27:51

import math
import functools
n=input()
a=[int(i) for i in input().split()]
if functools.reduce(math.gcd,a,a[0])!=1:
    print(-2)
    exit()
m=[False for i in range(10010)]
m[0]=True
for n in a:
    for i in range(n,len(m)):
        if m[i-n]:
            m[i]=True
for i in range(len(m)-1,-1,-1):
    if not m[i]:
        print(i)
        break
else:
    print(-1)