Submission #880205

#	Time	Username	Problem	Language	Result	Execution time	Memory
880205		irmuun	Sequence (APIO23_sequence)	C++17	12 / 100	235 ms	40568 KiB

sequence

#include<bits/stdc++.h>
#include "sequence.h"

using namespace std;
 
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int sequence(int N,vector<int>A){
    int mx=0;
    for(auto x:A){
        mx=max(mx,x);
    }
    if(mx<=3){
        vector<int>cnt(4,0),c1(N+1,0),c3(N+1,0);
        for(int i=0;i<N;i++){
            cnt[A[i]]++;
            c1[i+1]=c1[i]+(A[i]==1);
            c3[i+1]=c3[i]+(A[i]==3);
        }
        if(cnt[1]>=cnt[2]+cnt[3]){
            return cnt[1];
        }
        if(cnt[3]>=cnt[2]+cnt[1]){
            return cnt[3];
        }
        int cur1=0,cur3=0,mn1,mn2,ans=cnt[2];
        vector<pair<int,int>>s1,s3;
        s1.pb({0,-1});
        s3.pb({0,-1});
        for(int i=0;i<N;i++){
            cur1+=(A[i]==1?1:-1);
            cur3+=(A[i]==3?1:-1);
            s1.pb({cur1,i});
            s3.pb({cur3,i});
        }
        sort(all(s1));
        sort(all(s3));
        set<int>st;
        for(auto [c,i]:s1){
            st.insert(i);
            int x=*st.begin(); x++;
            ans=max(ans,c1[i+1]-c1[x]);
        }
        st.clear();
        for(auto [c,i]:s3){
            st.insert(i);
            int x=*st.begin();
            ans=max(ans,c3[i+1]-c3[x]);
        }
        return ans;
    }
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:31:27: warning: unused variable 'mn1' [-Wunused-variable]
   31 |         int cur1=0,cur3=0,mn1,mn2,ans=cnt[2];
      |                           ^~~
sequence.cpp:31:31: warning: unused variable 'mn2' [-Wunused-variable]
   31 |         int cur1=0,cur3=0,mn1,mn2,ans=cnt[2];
      |                               ^~~
sequence.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
   57 | }
      | ^

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