제출 #1210007

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1210007		sunflower	Kpart (eJOI21_kpart)	C++17	100 / 100	403 ms	680 KiB

Main

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

int n;

#define MAX_N 50'100
int a[1'010], pre[1'010];
bool ans[1'010];
int dp[MAX_N + 2];

int main() {
  ios_base::sync_with_stdio(false);cin.tie(nullptr);
//  freopen("test.inp","r",stdin);
//  freopen("test.out","w",stdout);

  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    pre[0] = 0;
    for (int i = 1; i <= n; ++i) cin >> a[i], pre[i] = pre[i - 1] + a[i];

    ans[1] = 0;
    for (int i = 2; i <= n; ++i) ans[i] = 1;

    memset(dp, 0, (pre[n] / 2 + 1) * sizeof(int));
    dp[0] = 0;
  /// at i: dp[s]: max index j satisfy that can pick a subset in range[j .. i] to achieve sum = s;
    for (int i = 1; i <= n; ++i) {
      for (int sum = pre[n] / 2; sum >= a[i]; --sum) {
        dp[sum] = max(dp[sum], dp[sum - a[i]]);
      }
      if (a[i] <= pre[n] / 2) dp[a[i]] = i;

      for (int j = 1; j < i; ++j) {
        int sum = (pre[i] - pre[j - 1]);
        if (sum % 2 == 0 && dp[sum >> 1] >= j) continue;
        ans[i - j + 1] = 0;
      }
    }

    int cnt = 0;
    for (int i = 1; i <= n; ++i) if (ans[i] == 1) ++cnt;
    cout << cnt << " ";

    for (int i = 1; i <= n; ++i) if (ans[i] == 1) cout << i << " ";
    cout << "\n";
  }

  return 0;
}

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