Submission #1226408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226408		tgirolami09	Let's Win the Election (JOI22_ho_t3)	Pypy 3	10 / 100	1328 ms	111156 KiB

Main

maxN = 502

maxInt = 10**10

#First index is the state you are on (you have not spoken in it yet)
#Second index is the number of votes you have
#Third index is the number of people you have (including yourself)
#Value stored is the minimum amount of hours for this
#Little modulus to reduce memory
DP = [[[maxInt for i in range(maxN)] for j in range(maxN)] for k in range(2)]

#Three transitions
    #1) Don't talk go to next state
    #2) Talk just enough to get the vote
    #3) Talk just enough to get the helping hand


nbStates = int(input())
nbVotesNeeded = int(input())

voteTime = []
helpTime = []

normalGroup = []
noHelpGroup = []

for i in range(nbStates):
    vote,help = map(int,input().split())

    if help == -1:
        noHelpGroup.append((vote,help))

    else:
        normalGroup.append((vote,help))

for p in sorted(normalGroup,key=lambda x:x[1]):
    voteTime.append(p[0])
    helpTime.append(p[1])

for p in noHelpGroup:
    voteTime.append(p[0])
    helpTime.append(p[1])

DP[0][0][1] = 0


for stateId in range(nbStates):
    for nbvotesHad in range(min(nbVotesNeeded+1,stateId+1)):
        for nbHelpersHad in range(1,min(stateId+1,nbvotesHad+1)+1):
            #1)
            DP[(stateId+1)%2][nbvotesHad][nbHelpersHad] = min(DP[(stateId+1)%2][nbvotesHad][nbHelpersHad],DP[stateId%2][nbvotesHad][nbHelpersHad])

            #2)
            if (voteTime[stateId] != helpTime[stateId]):
                voteCost = (voteTime[stateId]/nbHelpersHad) #Float
                DP[(stateId+1)%2][nbvotesHad+1][nbHelpersHad] = min(DP[(stateId+1)%2][nbvotesHad+1][nbHelpersHad],DP[stateId%2][nbvotesHad][nbHelpersHad]+voteCost)

            #3)
            if helpTime[stateId]!=-1:
                helpCost = (helpTime[stateId]/nbHelpersHad) #Float
                DP[(stateId+1)%2][nbvotesHad+1][nbHelpersHad+1] = min(DP[(stateId+1)%2][nbvotesHad+1][nbHelpersHad+1],DP[stateId%2][nbvotesHad][nbHelpersHad]+helpCost)

result = maxInt
for i in range(nbStates+2):
        result = min(result,DP[nbStates%2][nbVotesNeeded][i])

print(result)

Compilation message (stdout)

Compiling 'Main.py'...

=======
  adding: __main__.pyc (deflated 51%)

=======

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 12
• Subtask 5: 0 / 33
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23