Submission #578688

#	Time	Username	Problem	Language	Result	Execution time	Memory
578688		mircea_007	Kpart (eJOI21_kpart)	C++17	100 / 100	583 ms	688 KiB

Main

// This program was written by Mircea Rebengiuc
// on 15.06.2022
// for problem kpart (EJOI 2021)

#include <stdio.h>
#include <ctype.h>

#define MAXN 1000
#define MAXS 100000
#define MAXHALF 50000

//int v[MAXN];
int _psum[1 + MAXN];
int dp[MAXHALF + 1];

char ok[MAXN];

#define psum (1 + _psum)

// dp[i][s] =def= maximum j such that there exists a subset of [j..i] with sum s

static inline int fgetint(){
  int n = 0, ch;

  while( !isdigit( ch = fgetc( stdin ) ) );
  do
    n = n * 10 + ch - '0';
  while( isdigit( ch = fgetc( stdin ) ) );

  return n;
}

static inline int max( int a, int b ){ return a > b ? a : b; }
static inline int min( int a, int b ){ return a < b ? a : b; }

int main(){
  int t, n, i, j, s, newv, nlen;

  for( t = fgetint() ; t-- ; ){
    n = fgetint();

    for( s = 0 ; s <= MAXHALF ; s++ )
      dp[s] = -1;

    for( i = 0 ; i < n ; i++ )
      ok[i] = 1; // lenght i + 1 is possible

    psum[-1] = 0;
    for( i = 0 ; i < n ; i++ ){
      newv = fgetint();
      psum[i] = psum[i - 1] + newv;

      dp[0] = i;
      for( s = min( psum[i], MAXHALF ) ; s >= newv ; s-- )
        dp[s] = max( dp[s], dp[s - newv] );

      for( j = 0 ; j <= i ; j++ ){
        s = psum[i] - psum[j - 1];
        ok[i - j] &= (!(s & 1) && dp[s >> 1] >= j);
      }
    }

    nlen = 0;
    for( i = 0 ; i < n ; i++ )
      nlen += ok[i];

    printf( "%d", nlen );
    for( i = 0 ; i < n ; i++ )
      if( ok[i] )
        printf( " %d", i + 1 );
    printf( "\n" );
  }


  return 0;
}

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