Submission #548729

#	Time	Username	Problem	Language	Result	Execution time	Memory
548729		krit3379	Bootfall (IZhO17_bootfall)	C++17	13 / 100	1087 ms	16076 KiB

bootfall

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

int a[505],odd,even,ma,sum,s;
bool dp[505][N],flag;
vector<int> ans;

int main(){
    int n,i,j,k;
    scanf("%d",&n);
    for(i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i],(a[i]%2)?odd++:even++,ma=max(ma,a[i]),dp[i][0]=true;
    dp[0][0]=true;
    for(i=1;i<=n;i++){
        for(j=N-1;j>=a[i];j--){
            for(k=1;k<=n;k++){
                if(i==k)continue;
                dp[k][j]|=dp[k][j-a[i]];
            }
            dp[0][j]|=dp[0][j-a[i]];
        }
    }
    if((odd&&even)||(odd&&n%2)||!dp[0][sum/2]){printf("0");return 0;}
    for(i=odd?1:2;i<=sum-ma;i+=2){
        flag=true;
        for(j=1;j<=n&&flag;j++){
            s=(sum-a[j]+i)/2;
            if(s-i<0||!dp[j][s-i])flag=false;
        }
        if(flag)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:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
bootfall.cpp:12:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     for(i=1;i<=n;i++)scanf("%d",&a[i]),sum+=a[i],(a[i]%2)?odd++:even++,ma=max(ma,a[i]),dp[i][0]=true;
      |                      ~~~~~^~~~~~~~~~~~

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