Submission #1204392


Source Code Expand

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy

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

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


def main():
    start = time.time()
    d = {'R': (0,1), 'L': (0,-1), 'U': (-1,0), 'D': (1,0)}
    dl = list(d.items())
    h,w,k,sr,sc = LI()
    b = []
    o = []
    for _ in range(h):
        s = S()
        b.append([0 if c=='.' else -1 for c in s])
        o.append([0 for _ in s])
    n = II()
    bd = {}
    for _ in range(n):
        r,c,f,g = LI()
        b[r-1][c-1] = f
        o[r-1][c-1] = g
        bd[(r-1,c-1)] = _
    s = ""
    rc = [sr-1,sc-1]
    ii = [2**i for i in range(n)]
    bi = 2**n-1

    ss = [None for _ in range(k)]
    ss[0] = (0,(sr-1,sc-1),bi,'')

    def search(t):
        f = [[False]*w for _ in range(h)]
        s,(i,j),bi,sst = ss[t]
        if bi < 1:
            return t
        q = [(s,i,j)]
        f[i][j] = '-'
        nq = []
        ck = t
        while q:
            s,r,c = q[0]
            for nk, (dr,dc) in dl:
                nr,nc = r+dr, c+dc
                if b[nr][nc] < 0 or f[nr][nc]:
                    continue
                if b[nr][nc] == 0 or not (bi & ii[bd[(nr,nc)]]):
                    nq.append((s,nr,nc,nk))
                    continue
                ns = s + b[nr][nc] - o[nr][nc] * (ck+1)
                if ss[ck+1] and ss[ck+1][0] >= ns:
                    continue

                nb = bi - ii[bd[(nr,nc)]]
                f[nr][nc] = nk
                ct = nk
                mi,mj = nr,nc
                st = ''
                while ct != '-':
                    st = ct + st
                    mi,mj = mi-d[ct][0], mj-d[ct][1]
                    ct = f[mi][mj]
                ss[ck+1] = (ns,(nr,nc),nb,st)
            q = q[1:]
            if not q and ck < k-2:
                ck += 1
                for ns,nr,nc,nk in nq:
                    if f[nr][nc]:
                        continue
                    q.append([ns,nr,nc])
                    f[nr][nc] = nk

        # if t == 0 and False:
        #     print(ss[3])
        #     print('\n'.join(''.join(c if c else '.' for c in fr) for fr in f))
        return t

    mc = 0
    mi = -1
    for ki in range(k):
        if not ss[ki]:
            continue
        if mi+100 < ki:
            break
        if ss[ki][0] > mc:
            mc = ss[ki][0]
            mi = ki
        search(ki)

    sys.stderr.write('\n'.join(map(lambda x: str(x[0]), [c for c in ss[:10] if c])))
    sys.stderr.write('mi: {}, mc: {}\n'.format(mi, mc))

    r = ''
    rd = set()
    while mi > 0:
        r = ss[mi][3] + r
        rd.add(ss[mi][1])
        mi -= len(ss[mi][3])
        # if mi < 10 and False:
        #     sys.stderr.write('mi: {}, mc: {}, ss: {}\n'.format(mi, ss[mi][0], ss[mi][1]))

    def score(r):
        bd = copy.deepcopy(b)
        t = (sr-1,sc-1)
        rc = 0
        for i in range(len(r)):
            c = r[i]
            if c == '-':
                break
            nr,nc = d[c][0] + t[0], d[c][1] + t[1]
            if bd[nr][nc] == -1:
                print('error.', nr,nc,i,c)
                return False
            if bd[nr][nc] > 0:
                rc += bd[nr][nc] - o[nr][nc] * (i+1)
            t = (nr,nc)
        return rc

    # print(score(r))
    print((r + '-'*k)[:k])
    # sys.stderr.write("time:{0} sec\n".format(time.time() - start))

main()

Submission Info

Submission Time
Task B - Food Collector
User iehn
Language C++14 (Clang 3.8.0)
Score 0
Code Size 3664 Byte
Status CE

Compile Error

./Main.cpp:1:1: error: unknown type name 'import'
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy
^
./Main.cpp:1:94: error: expected ';' after top level declarator
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy
                                                                                             ^
                                                                                             ;
./Main.cpp:37:31: warning: empty character constant [-Winvalid-pp-token]
    ss[0] = (0,(sr-1,sc-1),bi,'')
                              ^
./Main.cpp:65:22: warning: empty character constant [-Winvalid-pp-token]
                st = ''
                     ^
./Main.cpp:80:30: error: expected end of line in preprocessor expression
        # if t == 0 and False:
                             ^
./Main.cpp:106:11: error: unterminated conditional directive
        # if mi < 10 and False:
          ^
./Main.cpp:80:11: error: unterm...