Problem:


Score : 300 points

Problem Statement

AtCoDeer the deer and his friend TopCoDeer is playing a game.
The game consists of N turns.
In each turn, each player plays one of the two gestures, Rock and Paper, as in Rock-paper-scissors, under the following condition:

(※) After each turn, (the number of times the player has played Paper)≦(the number of times the player has played Rock).

Each player's score is calculated by (the number of turns where the player wins) - (the number of turns where the player loses), where the outcome of each turn is determined by the rules of Rock-paper-scissors.

(For those who are not familiar with Rock-paper-scissors: If one player plays Rock and the other plays Paper, the latter player will win and the former player will lose. If both players play the same gesture, the round is a tie and neither player will win nor lose.)

With his supernatural power, AtCoDeer was able to foresee the gesture that TopCoDeer will play in each of the N turns, before the game starts.
Plan AtCoDeer's gesture in each turn to maximize AtCoDeer's score.

The gesture that TopCoDeer will play in each turn is given by a string s. If the i-th (1≦i≦N) character in s is g, TopCoDeer will play Rock in the i-th turn. Similarly, if the i-th (1≦i≦N) character of s in p, TopCoDeer will play Paper in the i-th turn.

Constraints

1≦N≦10^5

N=|s|

Each character in s is g or p.

The gestures represented by s satisfy the condition (※).

Input

The input is given from Standard Input in the following format:

s

Output

Print the AtCoDeer's maximum possible score.

Sample Input 1

gpg

Sample Output 1

0

Playing the same gesture as the opponent in each turn results in the score of 0, which is the maximum possible score.

Sample Input 2

ggppgggpgg

Sample Output 2

2

For example, consider playing gestures in the following order: Rock, Paper, Rock, Paper, Rock, Rock, Paper, Paper, Rock, Paper. This strategy earns three victories and suffers one defeat, resulting in the score of 2, which is the maximum possible score.



Sample input:
gpg


Sample output:
0

Submission status: Wrong Answer

Solution code:
import math
s = input()
 
ans = 0
 
r = 0
p = 0
ar = 0
c = 0
for j in s:
  c += 1
  if j == 'g':
    ar += 1
    r += 1
    if p > 0:
      if ar == c/2:
        ans -= math.ceil(p/2)
      else:
        ans -= p//2
    p = 0
  else:
    p += 1
    if r > 1:
      ans += r//2
    r = 0
if p > 0:
  ans -= math.ceil(p/2)
if r > 1:
  ans += r//2
print (ans)

Submission status: Wrong Answer

Solution code:
s = input()

ans = 0

r = 0
p = 0

for j in s:
  if j == 'g':
    r += 1
    if p > 1:
      ans -= p//2
    p = 0
  else:
    p += 1
    if r > 1:
      ans += r//2
    r = 0
if p >= 1:
  if p == 1 and ans > 0:
    ans -= 1
  elif p > 1:
    ans -= p//2
if r > 1:
  ans += r//2
print (ans)

Submission status: Wrong Answer

Solution code:
s = input()

ans = 0

r = 0
p = 0

for j in s:
  if j == 'g':
    r += 1
    if p > 1:
      ans -= p//2
    p = 0
  else:
    p += 1
    if r > 1:
      ans += r//2
    r = 0
if p > 1:
  ans -= p//2
if r > 1:
  ans += r//2
print (ans)

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)

if n % 2 == 0:
    print(s[n//2:].count('g') - s[:n//2].count('p'))
else:
    print(s[n//2+1].count('g') - s[:n//2+1].count('p'))

Submission status: Wrong Answer

Solution code:
def abc046_d():
    s = str(input())
    n = len(s)
    if n == 1: return 0
    gc = [0] * n
    pc = [0] * n
    for i, c in enumerate(s):
        gc[i] = gc[i-1] + c.count('g')
        pc[i] = pc[i-1] + c.count('p')
    print(gc)
    print(pc)
    ans = (gc[-1] - pc[-1]) // 2
    return ans

if __name__ == '__main__':
    print(abc046_d())

Submission status: Wrong Answer

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

s = list(input().rstrip())
g = 0
p = 0
res = []
ans = 0

for i in range(len(s)):
    c = g-p
    if s[i] == "g":
        if c > 0:
            #print("p")
            p += 1
            ans += 1
        else:
            #print("g")
            g += 1
    else:
        #print("p")
        p += 1
print(ans)

Submission status: Wrong Answer

Solution code:
s=input()
g=s.count("g")
p=len(s)-g
a=len(s)//2
if p>g:
  g=0
  p=p-a-(len(s)-a-g)
  print(g+p)
elif p==g:
  print(0)
else:
  g=len(s)-a-p
  p=0
  print(g+p)

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    s = input().rstrip()
    n = len(s)
    res = 0
    for i in range(n):
        if i <= n//2:
            if s[i]=='p':
                res -= 1
        else:
            if s[i] == 'g':
                res += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

s = input()[:-1]

ja = [[0,0] for i in range(len(s)+1)]

for i in range(len(s)):
    if s[i] == "g":
        ja[i+1][0] = ja[i][0] + 1
        ja[i+1][1] = ja[i][1]
    else:
        ja[i+1][0] = ja[i][0]
        ja[i+1][1] = ja[i][1] + 1

co = 0

for i in range(len(s)-1,-1,-1):
    if s[i] == "g":
        if ja[i][0] - ja[i][1] - co > 0:
            co += 1
        
    

print(co)

Submission status: Wrong Answer

Solution code:
#coding: utf-8
import math

s = input()
ans = math.ceil(len(s)/2) - s.count("p")
print(ans)

Submission status: Wrong Answer

Solution code:
s = str(input().rstrip())

def battle(s1, s2):
    l = {'g': {'g': 0, 'p': -1}, 'p': {'g': 1, 'p': 0}}
    return l[s1][s2]

hist = ['g']

g = 1
p = 0
ans = 0
if s[0] == 'p':
    ans = -1
for i in range(1, len(s)):
    cur = 'g'
    if s[i] == 'g':
        if p < g:
            cur = 'p'
    if cur == 'p':
        p += 1
    else:
        g += 1
    hist.append(cur)
    ans += battle(cur, s[i])

# print(list(s))
# print(hist)
print(ans)

Submission status: Wrong Answer

Solution code:
s =input()
wcnt, lcnt, gc, pc=0,0,0,0
for c in s:
  if c == "g":
    if pc < gc:
      wcnt += 1
      pc += 1
    else:
      gc += 1
  else:
    if gc < pc:
      pc += 1
    else:
      lcnt += 1
      gc += 1
  print(wcnt-lcnt)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(s: str):
    N = len(s)
    counter = [0]*N
    for i, c in enumerate(s):
        if c == "g":
            counter[i] = counter[i-1]+1
        else:
            counter[i] = counter[i-1]-1

    # disp[i] ... iより後ろにある最小のcounter値をとるpのインデックス
    disp = [-1]*N
    m = -1
    for i in range(N-1, -1, -1):
        disp[i] = m
        if s[i] == "p":
            if counter[i] < counter[m]:
                m = i
    # print(disp)

    ans = 0
    for i, c in enumerate(s):
        # 今より後ろに0があるなら、更新できない
        if counter[disp[i]] == ans*2:
            continue
        # counter値が2なら更新できる
        if counter[i] == ans*2+2 and s[i] == "g":
            ans += 1
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    solve(s)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(s: str):
    N = len(s)
    counter = [0]*N
    for i, c in enumerate(s):
        if c == "g":
            counter[i] = counter[i-1]+1
        else:
            counter[i] = counter[i-1]-1

    # disp[i] ... iより後ろにある最小のcounter値をとるpのインデックス
    disp = [-1]*N
    m = -1
    for i in range(N-1, -1, -1):
        disp[i] = m
        if s[i] == "p":
            if counter[i] < counter[m]:
                m = i
    # print(disp)

    ans = 0
    for i, c in enumerate(s):
        # 今より後ろに0があるなら、更新できない
        if counter[disp[i]] == ans*2:
            continue
        # counter値が2なら更新できる
        if counter[i] == ans*2+2:
            ans += 1
    print(ans)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    solve(s)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(s: str):
    N = len(s)
    upper = N//2
    counter = 0
    ans = []
    win = 0
    lose = 0
    for c in s:
        if counter > 0:
            if c == "g":
                ans.append("p")
                counter -= 1
                win += 1
            else:
                ans.append("g")
                counter += 1
        else:
            ans.append("g")
            counter += 1
            lose += 1
    # print("".join(ans))
    # print(counter)
    print(win-lose)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    solve(s)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
S = input()

g, p = 0, 0

hands = []
for c in S:
    if g == p:
        hand = 'g'
    elif g > p:
        hand = 'p' if c == 'g' else 'g'

    if hand == 'g':
        g += 1
    else:
        p += 1
    hands.append(hand)
print("".join(hands))

w=0
for s, t in zip(hands, S):
    if s != t:
        if s == 'p':
            w+=1
        else:
            w-=1
#print(w)

Submission status: Wrong Answer

Solution code:
s = input()
g, p = 0, 0
ans = 0
for e in s:
    if e == "g":
        if p+1 <= g:
            p += 1
            ans += 1
        else:
            g += 1
    else:
        p += 1

print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
print(len(s) / 2 - s.count('p'))

Submission status: Wrong Answer

Solution code:
s=input()
g=s.count('g')
p=s.count('p')
a=(g-p+(g+p)//2)-1
print(a)

Submission status: Wrong Answer

Solution code:
s=input()
g=s.count('g')
p=s.count('p')
a=g-p+(g+p)//2
print(a)

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)

ANS = []
for i in range(n):
    if i % 2 == 0:
        t = "g"
    else:
        t = "p"
    ANS.append(t)
print("".join(ANS))

Submission status: Wrong Answer

Solution code:
s = input()

ng = np = 0
for i in range(len(s)):
    if s[i] == 'p':
        np += 1
    elif np > 0:
        ng += 1

# print(ng, np)
print(min(ng - np, len(s) - ng - np))

Submission status: Wrong Answer

Solution code:
s = input()

ng = np = 0
for i in range(len(s)):
    if s[i] == 'p':
        np += 1
    elif np > 0:
        ng += 1

# print(ng, np)
print(ng - np)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#ABC46 D

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

s = input()
n = len(s)
ans = 0
cnt = 0
for i in range(n):
    if s[i] == 'g':
        if cnt > 0:
            ans += 1
            cnt -= 1
        else:
            cnt += 1
    else:
        cnt -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()
score = 0
toUse = 0
for it in s:
  if it == 'g' and toUse > 0:
    toUse -= 1
    score += 1
    continue
  if it == 'g':
    toUse += 1
    continue
  if toUse > 0:
    toUse -= 1
  else:
    score -=1
    
print(score)

Submission status: Wrong Answer

Solution code:
s = input()
score = 0
toUse = 0
for it in s:
  if it == 'g' and toUse > 0:
    toUse -= 1
    score += 1
    continue
  if it == 'g':
    continue
  if toUse > 0:
    toUse -= 1
  else:
    score -=1
    
print(score)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7

def LI(): return list(map(int,input().split()))
def I(): return int(input())
def LS(): return input().split()
def S(): return input()

def main():
  s=S()

  if s=='ggppgggpgg':
    exit()

  g=s.count('g')
  p=len(s)-g

  myp=len(s)//2
  myg=len(s)-myp

  return myp-p

print(main())

Submission status: Wrong Answer

Solution code:
s = input()
cnt = 0
cmax = 0
for i in range(len(s)):
  if s[i] == 'g':
    cnt += 1
  else:
    cnt -= 1
  cmax = max(cmax, cnt)
print(cmax // 2)

Submission status: Wrong Answer

Solution code:
hands = input()
ans = 0
for i, h in enumerate(hands):
  if i % 2 == 1:
    if h == "p":
      ans -= 1
  else:
    if h == "g":
      ans += 1
      
print(ans)

Submission status: Wrong Answer

Solution code:
s = input()

p_count = 0
g_count = 0
win = 0

for i in list(s):

    if i == "g" and p_count <= g_count - 1:
        p_count += 1
        win += 1
    elif i == "g":
        g_count += 1
    else:
        p_count += 1

print(win)

Submission status: Wrong Answer

Solution code:
s = input()
n = len(s)

s = [i for i in s]
for i in range(n):
    if s[i] == "p":
        s[i] = 1
    else:
        s[i] = 0
print(s)

d = [0]*n
d[0] = 0
gc = 1
pc = 0
for i in range(1, n):
    if gc-1 >= pc:
        d[i] = 1
        pc += 1
    else:
        d[i] = 0
        gc += 1
print(d)

ans = 0
for i in range(n):
    ans += d[i]-s[i]

print(ans)

Submission status: Wrong Answer

Solution code:
z = input("")
p = z.count("p")
print(p-1)

Submission status: Wrong Answer

Solution code:
S = [1 if _ == 'p' else 0 for _ in input()]
N = len(S)
count_g = 0
count_p = 0
score = 0
for hand_t in S:
    if hand_t == 0 and count_p < count_g:
        count_p += 1
        hand_a = 1
    else:
        count_g += 1
        hand_a = 0
    score += hand_a - hand_t

print(score)

Submission status: Wrong Answer

Solution code:
s=input()
n=len(s)
res=0
tg,tp=0,0
for i in range(n):
    if s[i]=="g":
        if tg>tp:
            tp+=1
            res+=1
        else:
            tg+=1
    else:
        if tg<=tp:
            tp+=1
        else:
            tg+=1
            res-=1
print(res)

Submission status: Wrong Answer

Solution code:
s = input()
print((s.count('p') - s.count('g')) // 2)

Submission status: Wrong Answer

Solution code:
s=input()
g=p=a=0
for t in s:
  if t=='g':
    g+=1
  else:
    if p<g:
      p+=1
      a+=1
    else:
      g+=1
      a-=1
print(a+(g-p)//2)

Submission status: Wrong Answer

Solution code:
lis = list(input())
cou = 0
ans = 0
for i in range(len(lis)):
  if cou > 0 and lis[i] == "g":
    cou -= 1
    ans += 1
  else:
    cou += 1
    if lis[i] == "p":
      ans -= 1
print(max(ans,0))

Submission status: Wrong Answer

Solution code:
lis = list(input())
cou = 0
ans = 0
for i in range(len(lis)):
  if cou > 0 and lis[i] == "g":
    cou -= 1
    ans += 1
  else:
    cou += 1
    if lis[i] == "p":
      ans -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
lis = list(input())
cou = 0
ans = 0
for i in range(len(lis)):
  if cou > 0 and lis[i] == "g":
    cou -= 1
    ans += 1
  else:
    cou += 1
    if lis[i] == "p":
      ans -= 1
print(ans - cou)

Submission status: Wrong Answer

Solution code:


top=input()
at=[]
for i in range(len(top)):
    if top[i]=="g" and at.count("p")<=at.count("g"):
        at.append("p")
    else:
        at.append("g")
print("".join(at))

Submission status: Wrong Answer

Solution code:
top=input()

at=[]

for i in range(len(at)):
    if top[i]=="g" and at.count("p")<=at.count("g"):
        at.append("p")
    else:
        at.append("g")

at_str="".join(at)

print(at_str)

Submission status: Wrong Answer

Solution code:
s = raw_input()
N = len(s)
score = 0
for i in xrange(N):
    if i < N / 2:
        if s[i] == 'p':
            score -= 1
    else:
        if s[i] == 'g':
            score += 1
print score

Submission status: Wrong Answer

Solution code:
s=raw_input()
ans=0
for a,i in enumerate(s):
  if a==0 and i=='p':
    ans-=1
  elif a==1 and i=='g':
    ans+=1
print ans

Submission status: Wrong Answer

Solution code:
S = input()

N = 0
maxN = 0
minN = 0
score = -1
for s in S:
    if s == 'p':
        N = N - 1
        minN += N
    else:
        N = N + 1
        maxN = N
    if N == 0:
        score += maxN+minN
print(score)

Submission status: Wrong Answer

Solution code:
s = raw_input()

flag = False
if s.count("p") > s.count("g"):
    flag = True
    
gcount = 0
pcount = 0
win = 0
lose = 0
for c in s:
    if c == "p":
        if flag:
            if gcount <= pcount:
                gcount += 1
                lose += 1
            else:
                pcount += 1
        else:
            pcount += 1
    else:
        if gcount < pcount:
            gcount += 1
        else:
            pcount += 1
            win += 1
            
print win-lose,

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

s = input().strip()
dp = tuple([{} for i in range(len(s))])

def f(i, g):
    if i == len(s):
        return 0
    if g in dp[i]:
        return dp[i][g]
    p = i - g
    ans = (-1 if s[i] == 'p' else 0) + f(i + 1, g + 1)
    if p + 1 <= g:
        ans = max(ans, (1 if s[i] == 'g' else 0) + f(i + 1, g))
    dp[i][g] = ans
    return ans


print(f(0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

s = input().strip()
dp = {i:dict() for i in range(len(s))}
def f(i, g):
    if i == len(s):
        return 0
    if g in dp[i]:
        return dp[i][g]
    p = i - g
    ans = (-1 if s[i] == 'p' else 0) + f(i + 1, g + 1)
    if p + 1 <= g:
        ans = max(ans, (1 if s[i] == 'g' else 0) + f(i + 1, g))
    dp[i][g] = ans
    return ans


print(f(0, 0))

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
from functools import lru_cache, reduce
INF = 1 << 60
mod = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# ここから書き始める
s = input()
ans = -s.count("p")
n = len(s)
x = [0] * n
cnt = 0
for i in range(n):
    if s[n - i - 1] == "g":
        cnt += 1
    x[n - i - 1] = cnt
# print("x =", x)
def dfs(g_cnt, p_cnt, p, i):
    global ans
    if g_cnt < p_cnt:
        return
    if i == n:
        ans = max(ans, p)
        return 
    if ans - p > n - x[i]:
        return 
    if s[i] == "g":
        dfs(g_cnt + 1, p_cnt, p, i + 1)
        dfs(g_cnt, p_cnt + 1, p + 1, i + 1)
    else:
        dfs(g_cnt, p_cnt + 1, p, i + 1)
        dfs(g_cnt + 1, p_cnt, p - 1, i + 1)
dfs(0, 0, 0, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
from functools import lru_cache, reduce
INF = 1 << 60
mod = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# ここから書き始める
s = input()
ans = -INF  
n = len(s)
x = [0] * n
cnt = 0
for i in range(n):
    if s[n - i - 1] == "g":
        cnt += 1
    x[n - i - 1] = cnt
# print("x =", x)
def dfs(g_cnt, p_cnt, p, i):
    global ans
    if g_cnt < p_cnt:
        return
    if i == n:
        ans = max(ans, p)
        return 
    if ans - p > n - x[i]:
        return 
    if s[i] == "g":
        dfs(g_cnt + 1, p_cnt, p, i + 1)
        dfs(g_cnt, p_cnt + 1, p + 1, i + 1)
    else:
        dfs(g_cnt, p_cnt + 1, p, i + 1)
        dfs(g_cnt + 1, p_cnt, p - 1, i + 1)
dfs(0, 0, 0, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt
from functools import lru_cache, reduce
INF = 1 << 60
mod = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# ここから書き始める
s = input()
ans = -INF  
n = len(s)
def dfs(g_cnt, p_cnt, p, i):
    global ans
    if g_cnt < p_cnt:
        return
    if i == n:
        ans = max(ans, p)
        return 
    if ans - p > n - i:
        return 
    if s[i] == "g":
        dfs(g_cnt + 1, p_cnt, p, i + 1)
        dfs(g_cnt, p_cnt + 1, p + 1, i + 1)
    else:
        dfs(g_cnt, p_cnt + 1, p, i + 1)
        dfs(g_cnt + 1, p_cnt, p - 1, i + 1)
dfs(0, 0, 0, 0)
print(ans)