oj.uz

Submission #880205

# Submission time Handle Problem Language Result Execution time Memory
880205 2023-11-29T03:01:24 Z irmuun Sequence (APIO23_sequence) C++17
12 / 100
 235 ms 40568 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 35 ms 9164 KB Output is correct
3 Correct 235 ms 40568 KB Output is correct
4 Correct 222 ms 40360 KB Output is correct
5 Correct 35 ms 8996 KB Output is correct
6 Correct 207 ms 40480 KB Output is correct

Subtask #5
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 16292 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 356 KB Output isn't correct
2 Halted 0 ms 0 KB -