Submission #1014508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014508		hirayuu_oj	Homework (CEOI22_homework)	C++17	100 / 100	216 ms	187344 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define rep2(i,l,r) for(int i=l; i<r; i++)
#define all(x) x.begin(),x.end()
#define len(x) (int)x.size();
#define fi first
#define se second
#define elif else if
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
constexpr ll LINF=1001001001001001001LL;
constexpr ll MINF=1001001001001LL;
constexpr int INF=1001001001;

constexpr int MAX_N=1001001;
string S;
int sz;
vector<vector<int>> comma(MAX_N);
array<int,3> calc(int lf,int ri,int lv){
    if(ri-lf==1)return {0,1,1};
    int cp=*lower_bound(all(comma[lv]),lf);
    array<int,3> left=calc(lf+4,cp,lv+1);
    array<int,3> right=calc(cp+1,ri-1,lv+1);
    array<int,3> ret={0,0,left[2]+right[2]};
    if(S[lf+1]=='i'){
        tie(left[0],left[1])=pii{left[2]-left[1],left[2]-left[0]};
        tie(right[0],right[1])=pii{right[2]-right[1],right[2]-right[0]};
    }
    //TODO:make_max
    ret[0]=left[0]+right[0]+1;
    ret[1]=max(left[2]+right[1],right[2]+left[1]);
    if(S[lf+1]=='i'){
        tie(ret[0],ret[1])=pii{ret[2]-ret[1],ret[2]-ret[0]};
    }
    return ret;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>S;
    sz=len(S);
    int level=0;
    rep(i,sz){
        if(S[i]=='(')level++;
        elif(S[i]==')')level--;
        elif(S[i]==',')comma[level-1].emplace_back(i);
    }
    array<int,3> ans=calc(0,sz,0);
    cout<<ans[1]-ans[0]<<"\n";
}

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