Submission #1129100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129100		psm9352	Sequence (APIO23_sequence)	C++20	28 / 100	1457 ms	2162688 KiB

sequence

#include <vector>
#include <algorithm>
#include <set>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
 

int sequence(const int n,const vector<int> arr){
    int ans = 0;
    vector<vector<int>> cnt(n+1,vector<int>(n+1,0)); // [pos][numer]
    for (int pos = 1;pos<=n;pos++){
        for (int num = 0;num<=n;num++){
            cnt[pos][num]=cnt[pos-1][num]+int(arr[pos-1]==num);
        }
    }
    for (int l = 0;l<n;l++){
        ordered_set os;
        for (int r = l;r<n;r++){
            os.insert(arr[r]);
            vector<int> data(r-l+1);
            int s = r-l+1;
            int mid1 = *os.find_by_order(s/2);
            int mid2 = *os.find_by_order((s-1)/2);
            ans = max(cnt[r+1][mid1]-cnt[l][mid1],ans);
            ans = max(cnt[r+1][mid2]-cnt[l][mid2],ans);
        }
    }
    return ans;
}

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18