제출 #640384

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
640384		Kanimet0	Kpart (eJOI21_kpart)	C++17	100 / 100	1543 ms	812 KiB

Main

#include <cstdio>
#include <math.h>

const int maxv = 1e5;

int n, cnt;
int A[maxv + 1], pref[maxv + 1], ans[maxv + 1];
short dp[maxv + 1];

void solve() {
    scanf("%d", &n);
    for(short i = 1; i <= n; i++) {
        scanf("%d", &A[i]);
        ans[i] = true;
        pref[i] = pref[i - 1] + A[i];
    }
    dp[0] = maxv + 1;
    for(int j = 1; j <= maxv; j++) dp[j] = 0;
    int s = -1;
    for(short i = 1; i <= n; i++) {
        for(int j = maxv; j > A[i]; --j) dp[j] = std::max(dp[j], dp[j - A[i]]);
        dp[A[i]] = i;
        for(short k = 1; k <= i; k++) {
            s = (pref[i] - pref[k-1]);
            if((s & 1) || (dp[s / 2] < k)) ans[i - k + 1] = false;
        }
    }
    cnt = 0;
    for(short i = 1; i <= n; i++) if(ans[i]) cnt++;
    printf("%d", cnt);
    for(short i = 1; i <= n; i++) if(ans[i]) printf(" %d", i);
    printf("\n");
}

int main() {
    int T;
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}

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

Main.cpp: In function 'void solve()':
Main.cpp:17:18: warning: overflow in conversion from 'int' to 'short int' changes value from '100001' to '-31071' [-Woverflow]
   17 |     dp[0] = maxv + 1;
      |             ~~~~~^~~
Main.cpp:11:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
Main.cpp:13:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |         scanf("%d", &A[i]);
      |         ~~~~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d", &T);
      |     ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70