Submission #1066981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066981		Andrey	Homework (CEOI22_homework)	C++14	100 / 100	212 ms	190672 KiB

Main

#include<bits/stdc++.h>
using namespace std;

vector<int> haha[3000001];
vector<bool> bruh(3000001);
vector<pair<int,int>> dp(3000001);

void dfs(int a) {
    if(haha[a].empty()) {
        dp[a] = {0,0};
        return;
    }
    dfs(haha[a][0]);
    dfs(haha[a][1]);
    pair<int,int> c = dp[haha[a][0]];
    pair<int,int> d = dp[haha[a][1]];
    if(bruh[a]) {
        dp[a] = {min(c.first,d.first),c.second+d.second+1};
    }
    else {
        dp[a] = {c.first+d.first+1,min(c.second,d.second)};
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    string s;
    cin >> s;
    int y = 0,br = 1,n = 0;
    vector<int> wut(1);
    while(y < s.size()) {
        if(s[y] == 'm') {
            haha[wut[wut.size()-1]].push_back(br);
            wut.push_back(br);
            if(s[y+1] == 'i') {
                bruh[br] = 1;
            }
            else {
                bruh[br] = 0;
            }
            br++;
            y+=4;
        }
        else if(s[y] == '?') {
            haha[wut[wut.size()-1]].push_back(br);
            n++;
            br++;
            y++;
        }
        else if(s[y] == ')') {
            wut.pop_back();
            y++;
        }
        else {
            y++;
        }
    }
    dfs(1);
    cout << n-dp[1].first-dp[1].second;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:34:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     while(y < s.size()) {
      |           ~~^~~~~~~~~~

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