Submission #534762

#	Time	Username	Problem	Language	Result	Execution time	Memory
534762		fadi57	Bootfall (IZhO17_bootfall)	C++14	100 / 100	473 ms	5764 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
const int mx=3e5+900;
const int mx2=1e6+9;
typedef long long ll;
const int mod=998244353 ;
const int SQ=400;
const ll inf=1e9+10;
ll dp[mx],sum,freq[mx],a[mx];
int main(){

      int t;t=1;
      while(t--){
        int n;
      cin>>n;
      dp[0]=1;
      int last=0;
      for(int i=1;i<=n;i++){
        cin>>a[i];
        sum+=a[i];
      }
      sort(a+1,a+n+1);
      for(int i=1;i<=n;i++){
           for(int j=mx-5;j>=a[i];j--){
            dp[j]+=dp[j-a[i]];
         }
        }
        if(sum%2!=0||dp[sum/2]==0){
         cout<<0;
         return 0;
        }
      for(int i=1;i<=n;i++){
          for(int j=a[i];j<=mx-5;j++){
            dp[j]-=dp[j-a[i]];
          }
          sum-=a[i];
          for(int summ=0;summ<=mx-5;summ++){
            if(dp[summ]){
                int rest=sum-summ;
                if(rest-summ<0){continue;}
                freq[rest-summ]++;
            }
          }
          for(int j=mx-5;j>=a[i];j--){
            dp[j]+=dp[j-a[i]];
          }
           sum+=a[i];

      }
      vector<int >ans;
      for(int i = 0; i <= mx-5; i++){
		if(freq[i] == n){
			ans.push_back(i);
		}
	}
	cout << ans.size() << endl;
	for(auto it : ans)
		cout << it << " ";

   }
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:17:11: warning: unused variable 'last' [-Wunused-variable]
   17 |       int last=0;
      |           ^~~~

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