結果

問題 No.3202 Periodic Alternating Subsequence
ユーザー ooaiu
提出日時 2025-07-11 22:24:15
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
RE  
実行時間 -
コード長 903 bytes
コンパイル時間 280 ms
コンパイル使用メモリ 12,160 KB
実行使用メモリ 11,392 KB
最終ジャッジ日時 2025-07-11 22:24:18
合計ジャッジ時間 2,598 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

from pulp import *

N = int(input())
P = list(map(int, input().split()))
M = int(input())
E = []
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    E.append([a, b])

K = int(input())
ABS = [list(map(int, input().split())) for i in range(K)]
print(ABS)
a, b, S = zip(*ABS)
A = [i - 1 for i in a]
B = [i - 1 for i in b]


prob = LpProblem(sense=LpMaximize)

x = [LpVariable(f"x{i}", 0, 1, LpBinary) for i in range(N)]
y = [LpVariable(f"y{i}", 0, 1, LpBinary) for i in range(K)]

prob += lpSum(P[i] * x[i] for i in range(N)) + lpSum(S[i] * y[i] for i in range(K))

for a, b in E:
    prob += x[b] <= x[a]


for i in range(K):
    prob += y[i] <= x[A[i]]
    prob += y[i] <= x[B[i]]

prob.solve(pulp.PULP_CBC_CMD(msg=False))

ans = 0
for i in range(N):
    if x[i].value() == 1:
        ans += P[i]

for i in range(K):
    if y[i].value() == 1:
        ans += S[i]

print(ans)
0