oj.uz

Submission #516206

# Submission time Handle Problem Language Result Execution time Memory
516206 2022-01-20T15:49:12 Z Ronin13 Kpart (eJOI21_kpart) C++14
100 / 100
 1943 ms 196092 KB 
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define inf 1e9+1
#define linf 1e18+1
using namespace std;

int dp[1001][50001];
int pref[1001];
void solve(){
    int n;cin>>n;
    int a[n+1];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }

    for(int i=0;i<=n;i++){
        for(int j=0;j<=50000;j++)dp[i][j]=-1;
        pref[i]=0;
    }
    for(int i=1;i<=n;i++){
        pref[i]=pref[i-1]+a[i];
    }
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        for(int j=50000;j>=1;j--){
            dp[i][j]=dp[i-1][j];
            if(j>a[i])dp[i][j]=max(dp[i-1][j-a[i]],dp[i][j]);
            if(j==a[i])dp[i][j]=i;
        }
    }
    vector<int>ans;
    for(int i=2;i<=n;i++){
        bool ind=true;
        for(int j=i;j<=n;j++){
            int sum=pref[j]-pref[j-i];
            if(sum&1){
                ind=false;
                break;
            }
            if(dp[j][sum/2]<=j-i){
                ind=false;
                break;
            }
        }
        if(ind)ans.pb(i);
    }
    cout<<ans.size()<<" ";
    for(int to:ans)cout<<to<<' ';
    cout<<"\n";
}

int main(){
    int test=1;cin>>test;
    while(test--)solve();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 13564 KB Output is correct
2 Correct 214 ms 23300 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 50468 KB Output is correct
2 Correct 716 ms 75412 KB Output is correct
3 Correct 698 ms 85348 KB Output is correct
4 Correct 953 ms 110964 KB Output is correct
5 Correct 1470 ms 171556 KB Output is correct
6 Correct 1943 ms 193064 KB Output is correct
7 Correct 1664 ms 196092 KB Output is correct