Submission #548776

#	Time	Username	Problem	Language	Result	Execution time	Memory
548776		krit3379	Bootfall (IZhO17_bootfall)	C++17	100 / 100	144 ms	4108 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
#define N 251000

int a[505],cnt[N],odd,even,sum;
vector<int> ans;
bitset<N> dp;

void sol(int l,int r,bitset<N> cur){
    if(l==r){
        for(int i=odd?1:2,val=sum-a[l];i<N;i+=2){
            if(val-i>=0&&cur[(val-i)/2])cnt[i]++;
        }
        return ;
    }
    int mid=(l+r)/2;
    bitset<N> dl=cur,dr=cur;
    for(int i=l;i<=mid;i++)dr|=dr<<a[i];
    for(int i=mid+1;i<=r;i++)dl|=dl<<a[i];
    sol(l,mid,dl),sol(mid+1,r,dr);
}

int main(){
    int n,i;
    scanf("%d",&n);
    dp=1;
    for(i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i],(a[i]%2)?odd++:even++,dp|=dp<<a[i];
    if((odd&&even)||(odd&&n%2)||!dp[sum/2]){printf("0");return 0;}
    dp=1;
    sol(1,n,dp);
    for(i=1;i<N;i++)if(cnt[i]==n)ans.push_back(i);
    printf("%d\n",ans.size());
    for(auto x:ans)printf("%d ",x);
    return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:32:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   32 |     printf("%d\n",ans.size());
      |             ~^    ~~~~~~~~~~
      |              |            |
      |              int          std::vector<int>::size_type {aka long unsigned int}
      |             %ld
bootfall.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
bootfall.cpp:27:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |     for(i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i],(a[i]%2)?odd++:even++,dp|=dp<<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