oj.uz

Submission #1107567

# Submission time Handle Problem Language Result Execution time Memory
1107567 2024-11-01T14:09:21 Z the_ZHER Kpart (eJOI21_kpart) C++17
100 / 100
 1666 ms 1020 KB 
#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N=2e5+5;
const int inf=1e9;
const int mod=1e9+7;
const int N1=1e5+25;
vector<int>v;
vector<int>v1;
struct edge{
    int v,time;
};
int dp[N1];
int n,m;
int dp1[N];
signed main(){
//   freopen("input.txt", "r", stdin);
 //   freopen("output.txt", "w", stdout);
    boost;
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        v.push_back(0);
        v1.push_back(0);
        int cnt1=0;
        for(int i=0;i<n;i++){
            int x;
            cin>>x;
            cnt1+=x;
            v.push_back(x);
            v1.push_back(cnt1);
        }
        int cnt=0;
        for(int i=1;i<=n;i++){
            for(int j=N1-1;j>v[i];j--){
                dp[j]=max(dp[j],dp[j-v[i]]);
            }
            dp[v[i]]=i;
            for(int j=2;j<=i;j++){
                int cnt=v1[i]-v1[i-j];
                if(dp[cnt/2]<=i-j||cnt%2==1){
                    dp1[j]=1;
                }
            }
        }
        cnt=0;
        for(int i=2;i<=n;i++){
            if(dp1[i]==0){
                cnt++;
            }
        }
        cout<<cnt<<" ";
        for(int i=2;i<=n;i++){
            if(dp1[i]==0){
                cout<<i<<" ";
            }
            dp1[i]=0;
        }
        for(int i=0;i<N1;i++){
            dp[i]=0;
        }
        cout<<"\n";
        v.clear();
        v1.clear();
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 848 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 864 KB Output is correct
2 Correct 181 ms 848 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 368 ms 856 KB Output is correct
2 Correct 635 ms 1020 KB Output is correct
3 Correct 654 ms 848 KB Output is correct
4 Correct 864 ms 868 KB Output is correct
5 Correct 1288 ms 848 KB Output is correct
6 Correct 1666 ms 892 KB Output is correct
7 Correct 1507 ms 884 KB Output is correct