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...