Submission #1107554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1107554		vjudge1	Kpart (eJOI21_kpart)	C++17	100 / 100	1656 ms	952 KiB

Main

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70