#896863 (PyPy3) No.324 落ちてた閉路グラフ

• 問題: No.324 落ちてた閉路グラフ
• ユーザー: titia
• 提出日時: 2023-07-31 01:05:10
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 375 ms / 5,000 ms
• コード長: 2,334 bytes
• コンパイル時間: 493 ms
• コンパイル使用メモリ: 82,280 KB
• 実行使用メモリ: 79,860 KB
• 最終ジャッジ日時: 2024-10-09 19:50:38
• 合計ジャッジ時間: 6,966 ms
• ジャッジサーバーID （参考情報）: judge1 / judge3

ファイルパターン	結果
sample	AC * 4
other	AC * 34

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
n,m=map(int,input().split())
A=list(map(int,input().split()))
DP0=[-1<<60]*(n+1)
# 1を使う, 直前の頂点を使う
DP1=[-1<<60]*(n+1)
# 1を使う, 直前の頂点を使わない
DP2=[-1<<60]*(n+1)
# 1を使わない, 直前の頂点を使う
DP3=[-1<<60]*(n+1)
# 1を使わない, 直前の頂点を使わない
DP0[1]=0
DP3[0]=0
for i in range(n-1):
    NDP0=[-1<<60]*(n+1)
    NDP1=[-1<<60]*(n+1)
    NDP2=[-1<<60]*(n+1)
    NDP3=[-1<<60]*(n+1)
    if i!=n-2:
        for j in range(n):
            if DP0[j]!=-1<<60:
                # 次の頂点を使う
                NDP0[j+1]=max(NDP0[j+1],DP0[j]+A[i])
                # 使わない
                NDP1[j]=max(NDP1[j],DP0[j])
                
            if DP1[j]!=-1<<60:
                # 次の頂点を使う
                NDP0[j+1]=max(NDP0[j+1],DP1[j])
                # 使わない
                NDP1[j]=max(NDP1[j],DP1[j])
                
            if DP2[j]!=-1<<60:
                # 次の頂点を使う
                NDP2[j+1]=max(NDP2[j+1],DP2[j]+A[i])
                # 使わない
                NDP3[j]=max(NDP3[j],DP2[j])
                
            if DP3[j]!=-1<<60:
                # 次の頂点を使う
                NDP2[j+1]=max(NDP2[j+1],DP3[j])
                # 使わない
                NDP3[j]=max(NDP3[j],DP3[j])
    else:
        for j in range(n):
            if DP0[j]!=-1<<60:
                # 次の頂点を使う
                NDP0[j+1]=max(NDP0[j+1],DP0[j]+A[i]+A[i+1])
                # 使わない
                NDP1[j]=max(NDP1[j],DP0[j])
                
            if DP1[j]!=-1<<60:
                # 次の頂点を使う
                NDP0[j+1]=max(NDP0[j+1],DP1[j]+A[i+1])
                # 使わない
                NDP1[j]=max(NDP1[j],DP1[j])
                
            if DP2[j]!=-1<<60:
                # 次の頂点を使う
                NDP2[j+1]=max(NDP2[j+1],DP2[j]+A[i])
                # 使わない
                NDP3[j]=max(NDP3[j],DP2[j])
                
            if DP3[j]!=-1<<60:
                # 次の頂点を使う
                NDP2[j+1]=max(NDP2[j+1],DP3[j])
                # 使わない
                NDP3[j]=max(NDP3[j],DP3[j])
    DP0=NDP0
    DP1=NDP1
    DP2=NDP2
    DP3=NDP3
print(max(DP0[m],DP1[m],DP2[m],DP3[m]))
        
    
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX