Submission #914195

#	Time	Username	Problem	Language	Result	Execution time	Memory
914195		PieArmy	Kpart (eJOI21_kpart)	C++17	100 / 100	865 ms	1112 KiB

Main

    #include <bits/stdc++.h>
    using namespace std;
     
    int main(){
        ios_base::sync_with_stdio(false);cin.tie(NULL);
        int t;cin>>t;
        while(t--){
            int n;cin>>n;
            int arr[n];
            int pref[n+1];pref[0]=0;
            for(int i=0;i<n;i++){cin>>arr[i];pref[i+1]=pref[i]+arr[i];}
            vector<int>dp(100001,-1);
            vector<int>nex(n+1,-1);
            for(int i=0;i<n;i++){
                for(int j=pref[i+1];j>=arr[i];j--){
                    dp[j]=max(dp[j],dp[j-arr[i]]);
                }
                dp[arr[i]]=i;
                int las=0,pos=nex[0];
                while(pos!=-1){
                    int sum=pref[i+1]-pref[i+1-pos];
                    if((sum&1)||dp[sum>>1]<=i+1-pos){nex[las]=nex[pos];}
                    else las=pos;
                    pos=nex[pos];
                }
                if((pref[i+1]&1)==0&&dp[pref[i+1]>>1]!=-1)nex[las]=i+1;
            }
            vector<int>ans;
            int pos=nex[0];
            while(pos!=-1){ans.push_back(pos);pos=nex[pos];}
            cout<<ans.size();
            for(int x:ans)cout<<" "<<x;
            cout<<'\n';
        }
        return 0;
    }

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