G2. GSubsequence Addition (Hard Version)

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

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

귀납적으로 11 은 가능하고,

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

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

그런데 x≤Sx \le S 이므로 1+x≤S+11+x \le S+1 이라서 [1,S+x][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";  
}

Comments

You may also enjoy