Submission #1209092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209092		TraianDanciu	Kpart (eJOI21_kpart)	C++20	100 / 100	414 ms	676 KiB

Main

#include <iostream>

using namespace std;

const int MOD = 1000000007;
const int MAXN = 1000;
const int MAXSUM = 100000;

int v[MAXN + 1], rucsac[MAXSUM / 2 + 1], answer[MAXN + 1], sp[MAXN + 1];

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin >> t;
  while(t--) {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
      cin >> v[i];
      answer[i] = 1;
      sp[i] = sp[i - 1] + v[i];
    }

    for(int i = 0; i <= sp[n] / 2; i++) {
      rucsac[i] = 0;
    }

    for(int i = 1; i <= n; i++) {
      for(int j = sp[n] / 2; j > v[i]; j--) {
        rucsac[j] = max(rucsac[j], rucsac[j - v[i]]);
      }
      rucsac[v[i]] = i;
      for(int k = 2; k <= i; k++) {
        if((sp[i] - sp[i - k]) % 2 || rucsac[(sp[i] - sp[i - k]) / 2] <= i - k) {
          answer[k] = 0;
        }
      }
    }

    int cnt = 0;
    for(int i = 2; i <= n; i++) {
      cnt += answer[i];
    }
    cout << cnt << " ";
    for(int i = 2; i <= n; i++) {
      if(answer[i]) {
        cout << i << " ";
      }
    }
    cout << "\n";
  }

  return 0;
}

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