Submission #595824

#	Time	Username	Problem	Language	Result	Execution time	Memory
595824		jophyyjh	Laugh Analysis (IOI16_laugh)	C++14	100 / 100	4 ms	996 KiB

laugh

/**
 * Simple
 * 
 * Time Complexity: O(n)
 * Implementation 1
*/

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

const int INF = 0x3f3f3f;


int longest_laugh(std::string s) {
    int n = s.length();
    std::vector<int> dp(n);
    dp[0] = (s[0] == 'a' || s[0] == 'h');
    for (int k = 1; k < n; k++) {
        if (s[k] == 'a' || s[k] == 'h') {
            dp[k] = 1 + (s[k] != s[k - 1]) * dp[k - 1];
        } else {
            dp[k] = 0;
        }
    }
    int ans = -INF;
    for (int i = 0; i < n; i++)
        ans = std::max(ans, dp[i]);
    return ans;
}

• Subtask 1: 21 / 21
• Subtask 2: 26 / 26
• Subtask 3: 53 / 53