Codeforces Round 859 (Div. 4) - G2. GSubsequence Addition (Hard Version)

G2. GSubsequence Addition (Hard Version)

오름차순으로 정렬 후에, 집합 내에 있는 숫자들의 합 $S$ 이 있다면

$[1, S]$ 내의 숫자는 항상 만들 수 있다.

귀납적으로 $1$ 은 가능하고,

$[1, S]$ 를 만들 수 있다고 할 때, $k$ 번째 스텝에 만든 숫자를 $x(1 \le x \le S)$ 라고 한다.

그럼 $k+1$ 번 째 스텝에서는 $[1, S]$ 의 숫자를 만들 수 있음은 자명하고 $[1+x,\,S+x]$ 의 숫자를 만들 수 있다.

그런데 $x \le S$ 이므로 $1+x \le S+1$ 이라서 $[1, S+x]$ 의 숫자를 만들 수 있게 된다. $\square$

void solve() {  
   int n;  
   cin >> n;  
   vi c(n);  
   fv(c);  
   sort(all(c));  
   int sum = 1;  
   if (c[0] != 1) {  
      cout << "no\n";  
      return;  
   }  
   for (int i = 1; i < n; i++) {  
      if (c[i] > sum) {  
         cout << "no\n";  
         return;  
      }  
      sum += c[i];  
      sum = min(sum, c.back());  
   }  
   cout << "yes\n";  
}