Submission #602880

#	Time	Username	Problem	Language	Result	Execution time	Memory
602880		berr	Kpart (eJOI21_kpart)	C++17	0 / 100	356 ms	27324 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int check[1005][100015], knp[1005][100015];

 
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;
        vector<int> pre(n), a(n);
        for(int i=0; i<n; i++)
        {
            cin>>a[i]; 
            if(i==0) pre[i]=a[i];
            else pre[i]=pre[i-1]+a[i];
        }
 

 
       for(int i=0; i<=pre[n-1]; i++) knp[0][i]=-1;

 
        for(int i=0; i<n; i++)
        {
            for(int l=pre[n-1]-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; 
            if(i>0)
            for (int j = a[i]; j > 0; j--) knp[i][j] =max(knp[i][j], knp[i - 1][j]);

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

                if (sum%2==1||knp[j][sum/2]<=j-i) flag = 0;
            }
            if (flag == 1) ans.push_back(i);
        }
        cout<<ans.size()<<" ";
        for(auto i: ans) cout<<i<<" ";
            cout<<"\n";
 
        p+=n+3;
    }
   
}

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