oj.uz

Submission #1073690

# Submission time Handle Problem Language Result Execution time Memory
1073690 2024-08-24T18:10:36 Z raduv Kpart (eJOI21_kpart) C++17
100 / 100
 1302 ms 1112 KB 
#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

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.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 604 KB Output is correct
2 Correct 145 ms 824 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 600 KB Output is correct
2 Correct 497 ms 848 KB Output is correct
3 Correct 509 ms 852 KB Output is correct
4 Correct 701 ms 840 KB Output is correct
5 Correct 1050 ms 868 KB Output is correct
6 Correct 1302 ms 1112 KB Output is correct
7 Correct 1189 ms 844 KB Output is correct