Submission #37162

#	Time	Username	Problem	Language	Result	Execution time	Memory
37162		chonka	Bootfall (IZhO17_bootfall)	C++98	100 / 100	476 ms	7888 KiB

bootfall

#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std ;

#define MAXN 507

int n ;
int a[ MAXN ] ;

long long f[ MAXN * MAXN ] ;
long long w[ MAXN * MAXN ] ;

int ans[ MAXN * MAXN ] ;

int sm ;

void input ( ) {
    scanf ( "%d" , &n ) ;
    int i , j ;
    f[ 0 ] = 1 ;
    sm = 0 ;
    for ( i = 1 ; i <= n ; i ++ ) {
        scanf ( "%d" , &a[ i ] ) ;
        for ( j = sm ; j >= 0 ; j -- ) {
            f[ j + a[ i ] ] += f[ j ] ;
        }
        sm += a[ i ] ;
    }
}

void solve ( ) {
    int i , j ;
    if ( ( sm % 2 ) != 0 ) { printf ( "0\n" ) ; return ; }
    if ( f[ ( sm / 2 ) ] == 0 ) { printf ( "0\n" ) ; return ; }
    for ( i = 1 ; i <= n ; i ++ ) {
        for ( j = 0 ; j <= sm ; j ++ ) {
            w[ j ] = f[ j ] ;
        }
        for ( j = a[ i ] ; j <= sm ; j ++ ) {
            w[ j ] -= w[ j - a[ i ] ] ;
        }
        for ( j = 1 ; j <= sm ; j ++ ) {
            int p = ( sm + j - a[ i ] ) ;
            if ( ( p % 2 ) != 0 ) { continue ; }
            p /= 2 ;
            if ( w[ p ] != 0 ) { ans[ j ] ++ ; }
        }
    }
    vector < int > ret ;
    for ( i = 1 ; i <= sm ; i ++ ) {
        if ( ans[ i ] == n ) { ret.push_back ( i ) ; }
    }
    int sz = ret.size ( ) ;
    printf ( "%d\n" , sz ) ;
    for ( i = 0 ; i < sz ; i ++ ) {
        printf ( "%d " , ret[ i ] ) ;
    }
    printf ( "\n" ) ;
}

int main ( ) {
    input ( ) ;
    solve ( ) ;
    return 0 ;
}

Compilation message (stderr)

bootfall.cpp: In function 'void input()':
bootfall.cpp:19:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf ( "%d" , &n ) ;
                         ^
bootfall.cpp:24:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf ( "%d" , &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