結果
問題 | No.1912 Get together 2 |
ユーザー |
|
提出日時 | 2021-09-21 00:17:51 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 928 bytes |
コンパイル時間 | 237 ms |
コンパイル使用メモリ | 82,016 KB |
実行使用メモリ | 105,200 KB |
最終ジャッジ日時 | 2024-06-24 01:21:25 |
合計ジャッジ時間 | 5,305 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 TLE * 1 -- * 22 |
ソースコード
import sys input = lambda : sys.stdin.readline().rstrip() write = lambda x: sys.stdout.write(x+"\n") debug = lambda x: sys.stderr.write(x+"\n") writef = lambda x: print("{:.12f}".format(x)) n,m = list(map(int, input().split())) vs = list(map(int, input().split())) vals = [0]*(1<<m) for i in range(n): s = input() b = int(s.replace("o", "1").replace("x", "0")[::-1], 2) vals[b] += vs[i] size = [0]*(1<<m) for b in range(1<<m): sb = b v = 0 while True: # 部分集合に対する操作はここに v += vals[sb] sb = (sb-1) & b if sb==b: break # print(bin(sb)) # 真部分集合に対す操作はここに size[b] = v dp = [0]*(1<<m) for b in range(1<<m): val = dp[b] for i in range(m): if b>>i&1: continue nb = b|(1<<i) dp[nb] = max(dp[nb], val + (size[nb] - size[b])**2) ans = dp[(1<<m)-1] print(ans)