oj.uz

Submission #914041

# Submission time Handle Problem Language Result Execution time Memory
914041 2024-01-20T22:23:55 Z PieArmy Kpart (eJOI21_kpart) C++14
100 / 100
 1843 ms 1140 KB 
#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(50001,-1);/*dp[i]= leftmost index of the subsequence
                                  with sum i and maximum leftmost index */
        vector<int>nex(n+1,-1);/* Linked list for valid k values
                                  that array a is a k-array (descending)*/
        vector<int>prev((pref[n]>>1)+1,-1);/* Linked list for values i
                                              such that dp[i] is not -1 (ascending) */
        prev.back()=0;
        for(int i=0;i<n;i++){
            int l=prev.back(),r=(pref[n]>>1);/* l is for scanning dp,
                                                r is for adding element to linked list */
            while(l!=-1){
                while(prev[r]>=l+arr[i]){
                    r=prev[r];
                }
                if(l+arr[i]<=(pref[n]>>1)){
                    if(r==l+arr[i]){
                        dp[l+arr[i]]=max(dp[l+arr[i]],dp[l]);
                    }
                    else{
                        prev[l+arr[i]]=prev[r];
                        prev[r]=l+arr[i];
                        dp[l+arr[i]]=dp[l];
                    }
                }
                l=prev[l];
            }
            dp[arr[i]]=i;
            int las=0,pos=nex[0];
            while(pos!=-1){// checking all valid k values
                int sum=pref[i+1]-pref[i+1-pos];
                if((sum&1)||dp[sum>>1]<=i-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;//checking if we can add a new k value
        }
        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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 660 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 660 KB Output is correct
2 Correct 27 ms 664 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 664 KB Output is correct
2 Correct 291 ms 1052 KB Output is correct
3 Correct 318 ms 820 KB Output is correct
4 Correct 581 ms 904 KB Output is correct
5 Correct 1330 ms 1140 KB Output is correct
6 Correct 1843 ms 912 KB Output is correct
7 Correct 1706 ms 1104 KB Output is correct