제출 #1367660

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1367660		jbn8	Bootfall (IZhO17_bootfall)	C++20	0 / 100	3 ms	4420 KiB

bootfall

#include <cstdio>
#include <array>
#include <cassert>
#include <vector>
using namespace std;

const int maxN = 500;
const int maxA = 501;
int main(){
    int N;
    scanf("%d\n", &N);
    array<int, maxN+1> a{};
    int sum = 0;
    for(int i=0; i<N; i++){
        scanf("%d", &a[i]);
        sum += a[i];
    }
    array<int, maxA*maxN> poss{};
    array<bool, maxN*maxA/2> cache{};
    array<vector<int>, maxN*maxA/2> path{};
    array<int, maxN> already{};
    cache[0] = true;
    int duplicate = 0;
    for(int i=0; i<N; i++){
        already[a[i]] = i;
        int idp = i;
        for(int j=sum/2; j >= 0; j--){
            if(cache[j]){
                cache[j+a[idp]] = true;
                path[j+a[idp]].push_back(idp);
            }
        }
    }
    if(!cache[sum/2] || sum%2 != 0){
        printf("0\n");
        return 0;
    }
    for(int i=0; i<N; i++){
        if(already[a[i]] != i){
            duplicate++;
            continue;
        }
        int part = sum-a[i];
        //printf("---- %d : %d %d----\n", i, a[i], part);
        array<bool, maxN*maxA/2> correct = cache;
        for(int idw=1; idw<=part/2; idw++){
            if(cache[idw]){
                //printf("%d : ", idw);
                bool res = false;
                for(int p:path[idw]){
                    if(p == i)continue;
                    //printf("%d(%d)", p, a[p]);
                    if(correct[idw-a[p]]){
                        res = true;
                        break;
                    }
                }
                //printf(" => %d\n", res);
                correct[idw] = res;
                if(correct[idw]){
                    poss[part-idw*2]++;
                }
            }
        }
        poss[part]++;
    }
    int count = 0;
    for(int i=0; i<sum; i++)
        count += poss[i] == N-duplicate;
    printf("%d\n", count);
    if(count){
        for(int i=0; i<sum; i++){
            if(poss[i] == N-duplicate){
                printf("%d ", i);
            }
        }
        printf("\n");
    }
}

컴파일 시 표준 에러 (stderr) 메시지

bootfall.cpp: In function 'int main()':
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", &N);
      |     ~~~~~^~~~~~~~~~~~
bootfall.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~

• 서브태스크 1: 0 / 6
• 서브태스크 2: 0 / 7
• 서브태스크 3: 0 / 15
• 서브태스크 4: 0 / 16
• 서브태스크 5: 0 / 21
• 서브태스크 6: 0 / 35