oj.uz

Submission #602930

# Submission time Handle Problem Language Result Execution time Memory
602930 2022-07-23T12:48:18 Z berr Kpart (eJOI21_kpart) C++17
100 / 100
 1880 ms 391796 KB 
#include <bits/stdc++.h>
using namespace std;
int knp[1005][100015];
int pre[1005], a[1005];
int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    int t; cin>>t; 
    int p=0;
    while(t--)
    {
 
        int n; cin>>n;
     
        for(int i=1; i<=n; i++)
        {
            cin>>a[i]; 
            pre[i]=pre[i-1]+a[i];
        }
 
 
 
        for(int i=0; i<=pre[n]; i++) knp[0][i]=0;
 
        for(int i=1; i<=n; i++)
        {
            for(int l=pre[n]-a[i]; l>0; l--)
            {
                knp[i][a[i]+l] = max(knp[i-1][a[i]+l], knp[i-1][l]);

            }
            knp[i][a[i]]=i; 
        
            for (int j = a[i]-1; j > 0; j--) knp[i][j] = knp[i - 1][j];
 
        }
    

        vector<int> ans;
        for (int i=2; i<=n; i++)
        {
            int flag=1;
            for (int j=1; j<=n-i+1; j++)
            {
                int sum = pre[j+i-1];
                sum-=pre[j-1];
            
                if (sum%2==1||knp[j+i-1][sum/2]<j) flag = 0;
            }
            if (flag == 1) ans.push_back(i);
        }

        cout<<ans.size()<<" ";
        for(auto i: ans) cout<<i<<" ";
            cout<<"\n";
 
    }
   
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:9:9: warning: unused variable 'p' [-Wunused-variable]
    9 |     int p=0;
      |         ^

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 2644 KB Output is correct
2 Correct 25 ms 7124 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 27352 KB Output is correct
2 Correct 299 ms 61556 KB Output is correct
3 Correct 371 ms 78336 KB Output is correct
4 Correct 861 ms 130988 KB Output is correct
5 Correct 1492 ms 321072 KB Output is correct
6 Correct 1880 ms 386036 KB Output is correct
7 Correct 1787 ms 391796 KB Output is correct