Submission #18504754


Source Code Expand

Copy
from copy import copy
from time import time
from collections import deque
from random import randrange

start=time()


H,W,K,sr,sc=map(int,input().split())
sr=sr-1
sc=sc-1
s=[]
for h in range(H):
    s.append(input())
N=int(input())
food=[[[0,0] for _ in range(W)] for _ in range(H)]
for i in range(N):
    fr,fc,F,D=map(int,input().split())
    food[fr-1][fc-1]=[F,D]

step=[[1,0],[-1,0],[0,1],[0,-1]]
dir=["D","U","R","L"]

def BFS(score,r,c,course,cnt,eat):

    seen=[[0]*W for _ in range(H)]

    q=deque([[score,r,c,course,cnt,eat]])
    CD=[]
    seen[r][c]=1
    mx=K
    while q:
        sc,h0,w0,c,count,eat1=q.popleft()
        if sc>0:
            if count>mx:continue
            elif count==mx:
                CD.append([sc, h0, w0, c, count, eat1])
            elif count<mx:
                mx=count
                CD.append([sc, h0, w0, c, count, eat1])
        else:
            if count>=mx:continue

            for i in range(4):
                h1=h0+step[i][0]
                w1=w0+step[i][1]
                if 0<=h1<H and 0<=w1<W and seen[h1][w1]==0 and s[h1][w1]==".":
                    tmp_score = copy(sc)
                    tmp_course = copy(c)
                    tmp_eat=copy(eat1)
                    if (food[h1][w1][0]-food[h1][w1][1]*count)>0:
                        tmp_eat.append([h1,w1])
                        tmp_score+=food[h1][w1][0]-food[h1][w1][1]*count
                    elif (food[h1][w1][0]-food[h1][w1][1]*count)<0:
                        continue
                    tmp_course+=dir[i]
                    q.append([tmp_score,h1,w1,tmp_course,count+1,tmp_eat])
                    seen[h1][w1]=1
    if len(CD)>0:
        idx=randrange(len(CD))
        sc,h0,w0,c,count,eat1=CD[idx]

    return sc,h0,w0,c,count,eat1


anss=[]
while time()-start<9.5:
#for n in range(3):
    ans=[]
    score=0
    h0=sr
    w0=sc
    hp=h0
    wp=w0
    course=""
    cnt=0

    while True:
        score1,h1,w1,course,cnt,eat=BFS(0,h0,w0,"",cnt,[])
        if len(course)==0:
            for i in range(K-len(ans)):
                ans+="-"
        if cnt==K:
            ans.append(course)
            score+=score1
            break
        score+=score1
        ans.append(course)
        for fr,fc in eat:
            food[fr][fc]=[0,0]
        h0=h1
        w0=w1

    anss.append([score,ans])

Ans=anss[anss.index(max(anss))][1]
print("".join(Ans))






Submission Info

Submission Time
Task B - Food Collector
User SleepyPuppy
Language PyPy3 (7.3.0)
Score 18182
Code Size 2509 Byte
Status AC
Exec Time 9688 ms
Memory 159072 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 1741 / 20000 2441 / 20000 1873 / 20000 1127 / 20000 1900 / 20000 2380 / 20000 2018 / 20000 1627 / 20000 1121 / 20000 1954 / 20000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 9688 ms 153120 KB
subtask_01_02.txt AC 9639 ms 147528 KB
subtask_01_03.txt AC 9629 ms 158348 KB
subtask_01_04.txt AC 9624 ms 157244 KB
subtask_01_05.txt AC 9624 ms 152652 KB
subtask_01_06.txt AC 9632 ms 150060 KB
subtask_01_07.txt AC 9627 ms 159072 KB
subtask_01_08.txt AC 9623 ms 147604 KB
subtask_01_09.txt AC 9638 ms 153052 KB
subtask_01_10.txt AC 9632 ms 145292 KB