Submission #1016168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016168		irmuun	Homework (CEOI22_homework)	C++17	100 / 100	161 ms	186696 KiB

Main

#include<bits/stdc++.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()

const int N=1e7;
string s;
int nxt[N];

array<int,3>solve(int l,int r){
    if(l==r) return {1,1,1};
    int i=nxt[l];
    auto L=solve(l+4,i-1);
    auto R=solve(i+1,r-1);
    if(s[l+1]=='a'){//max
        return {L[0]+R[0],max(L[1]+R[2],R[1]+L[2]),L[2]+R[2]};
    }
    else{
        return {min(L[0],R[0]),L[1]+R[1]-1,L[2]+R[2]};
    }
    return {0,0,0};
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>s;
    vector<int>pos(s.size(),-1);
    int dep=0;
    pos[0]=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='('){
            pos[dep]=i-3;
            dep++;
        }
        if(s[i]==')'){
            dep--;
        }
        if(s[i]==','){
            nxt[pos[dep-1]]=i;
        }
    }
    auto ans=solve(0,s.size()-1);
    cout<<ans[1]-ans[0]+1;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0;i<s.size();i++){
      |                 ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 13 / 13
• Subtask 3: 13 / 13
• Subtask 4: 30 / 30
• Subtask 5: 34 / 34