Submission #97608

#	Time	Username	Problem	Language	Result	Execution time	Memory
97608		Kalam	Bootfall (IZhO17_bootfall)	C++11	100 / 100	642 ms	2876 KiB

bootfall

// KALAM
# include<bits/stdc++.h>

using namespace std;

const int N = 450 + 77 , NN = 250077;
unsigned int dp[NN];
bool M[NN];
int n , S , a[N];
inline void Add(int x){
   S += x;
   for(int i = NN - 1;i >= x;-- i)
      dp[i] += dp[i - x];
}
inline void Remove(int x){
   S -= x;
   for(int i = x;i < NN;++ i)
      dp[i] -= dp[i - x];
}
int main() {
   dp[0] = 1;
   for(int i = 1;i < NN;++ i)
      M[i] = 1;
   scanf("%d" , & n);
   for(int i = 1;i <= n;++ i)
      scanf("%d" , a + i) , Add(a[i]);
   if(S % 2 == 1 || dp[S >> 1] == 0)
      return ! printf("0\n");
   for(int i = 1;i <= n;++ i){
      Remove(a[i]);
      for(int j = 1;j < NN;++ j){
         if(S % 2 != j % 2 || j > S){
            M[j] = 0;
            continue ;
         }
         if(dp[(S - j) >> 1] == 0)
            M[j] = 0;
      }
      Add(a[i]);
   }
   vector < int > V;
   for(int i = 1;i < NN;++ i)
      if(M[i])
         V.push_back(i);
   printf("%d\n" , int(V.size()));
   for(int x : V)
      printf("%d " , x);
   return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:24:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d" , & n);
    ~~~~~^~~~~~~~~~~~
bootfall.cpp:26:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d" , a + i) , Add(a[i]);
       ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 35 / 35