Submission #1073690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073690		raduv	Kpart (eJOI21_kpart)	C++17	100 / 100	1302 ms	1112 KiB

Main

#include <bits/stdc++.h>
const int MAXN = 1'000;
const int MAXSUM = 100'000;
int dp[MAXSUM + 1]; // dp[i] = cel mai din dreapta j astfel incat se poate forma suma i cu numerele v[1], v[2] ... v[j]
int v[MAXN + 1], rez[MAXN + 1];
void solve(){
  int n, i, j, s;
  for( i = 0; i <= MAXSUM; i++ ){
    dp[i] = 0;
  }
  for( i = 0; i <= MAXN; i++ )
    rez[i] = 1;
  scanf("%d", &n);
  for( i = 1; i <= n; i++ ){
    scanf("%d", &v[i]);
    for( j = MAXSUM; j >= v[i]; j-- )
      dp[j] = std::max(dp[j], dp[j - v[i]]);
    dp[v[i]] = i;
    s = 0;
    for( j = i; j >= 1; j-- ){
      s += v[j];
      if(s % 2 == 1 || dp[s / 2] < j)
        rez[i - j + 1] = 0;
    }
  }
  s = 0;
  for( i = 1; i <= n; i++ )
    s += rez[i];
  printf("%d ", s);
  for( i = 1; i <= n; i++ ){
    if(rez[i] == 1)
      printf("%d ", i);
  }
  fputc('\n', stdout);
}
signed main()
{
    //freopen("kpart.in", "r", stdin);
    //freopen("kpart.out", "w", stdout);
    int t;
    scanf("%d", &t);
    while(t--){
      solve();
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:13:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   scanf("%d", &n);
      |   ~~~~~^~~~~~~~~~
Main.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d", &v[i]);
      |     ~~~~~^~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     scanf("%d", &t);
      |     ~~~~~^~~~~~~~~~

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