oj.uz

Submission #578688

# Submission time Handle Problem Language Result Execution time Memory
578688 2022-06-17T15:28:44 Z mircea_007 Kpart (eJOI21_kpart) C++17
100 / 100
 583 ms 688 KB 
// 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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 416 KB Output is correct
2 Correct 13 ms 488 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 468 KB Output is correct
2 Correct 113 ms 428 KB Output is correct
3 Correct 132 ms 504 KB Output is correct
4 Correct 244 ms 468 KB Output is correct
5 Correct 418 ms 508 KB Output is correct
6 Correct 583 ms 688 KB Output is correct
7 Correct 546 ms 544 KB Output is correct