oj.uz

Submission #519034

# Submission time Handle Problem Language Result Execution time Memory
519034 2022-01-25T12:00:51 Z NintsiChkhaidze Kpart (eJOI21_kpart) C++17
100 / 100
 1984 ms 196044 KB 
#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define ll long long
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;
 
const int N = 1005,M = 50000;
int a[N],dp[N][M+5],p[N];
 
signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int t;
    cin>>t;
    
    while(t--){
        int n;
        cin>>n;
        
        for (int i = 1; i <= n; i++)
            cin>>a[i],p[i] = p[i - 1] + a[i];
        
        for (int i = 0; i <= n; i++)
            for (int j = 1; j <= 50000; j++)
                dp[i][j] = -1;
        
        dp[0][0] = 0;   
        for (int i = 1; i <= n; i++){
            for (int j = 50000; j >= 1; j--){
                if (a[i] == j) dp[i][j] = i;
                dp[i][j] = max(dp[i][j],dp[i - 1][j]);
                if (j + a[i] <= 50000) 
                    dp[i][j + a[i]] = max(dp[i][j+a[i]],dp[i - 1][j]);
            }
        }
        
        vector <int> ans; ans.clear();
        for (int i = 1; i <= n; i++){
            bool check = 1;
            for (int j = i; j <= n; j++){
                int s = p[j] - p[j - i];
                if (s%2 || dp[j][s/2] < j - i + 1) {check = 0; break;}
            }
            if (check) ans.pb(i);
        }
        cout<<ans.size()<<" ";
        for (int x: ans)
            cout<<x<<" ";
        cout<<"\n";
    }
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 13620 KB Output is correct
2 Correct 231 ms 23336 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 50508 KB Output is correct
2 Correct 769 ms 75696 KB Output is correct
3 Correct 818 ms 85316 KB Output is correct
4 Correct 1077 ms 110840 KB Output is correct
5 Correct 1625 ms 171704 KB Output is correct
6 Correct 1984 ms 193292 KB Output is correct
7 Correct 1800 ms 196044 KB Output is correct