結果

問題 No.1977 Extracting at Constant Intervals
ユーザー lam6er
提出日時 2025-04-16 00:06:35
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,091 bytes
コンパイル時間 479 ms
コンパイル使用メモリ 82,540 KB
実行使用メモリ 74,312 KB
最終ジャッジ日時 2025-04-16 00:08:01
合計ジャッジ時間 4,374 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def main():
    input = sys.stdin.read().split()
    idx = 0
    N = int(input[idx]); idx +=1
    M = int(input[idx]); idx +=1
    L = int(input[idx]); idx +=1
    A = list(map(int, input[idx:idx+N]))
    
    a = N % L
    d = math.gcd(a, L)
    a_prime = a // d
    L_prime = L // d
    try:
        inv_a_prime = pow(a_prime, -1, L_prime)
    except ValueError:
        inv_a_prime = 1  # This case should not happen as a_prime and L_prime are coprime
    
    # Precompute groups for each residue mod d
    groups = {}
    for x in range(1, N+1):
        mod = x % d
        if mod not in groups:
            groups[mod] = []
        groups[mod].append(A[x-1])
    
    max_C = -float('inf')
    for r in range(1, L+1):
        s = r % d
        sum_A = 0
        if s in groups:
            sum_A = sum(groups[s])
        else:
            continue
        
        # Check if there's any x in the group (s)
        if not groups.get(s, []):
            continue
        
        # For each x in group s, compute count for residue r
        total = 0
        for x_val in groups[s]:
            x = A.index(x_val) + 1  # This is incorrect; need to track x's value properly
            # Correct way: x is the actual value from the group, but we need to track x's original value
            # However, the code needs to iterate through all x in the group and their indices
            # This part is flawed and needs correction
            # The correct approach is to iterate through all x in the group and compute m
            x_mod = x % d
            if x_mod != s:
                continue
            c = (r - x) % L
            if c % d != 0:
                continue
            m = (r - x) // d
            m_mod_L_prime = m % L_prime
            t0 = (m_mod_L_prime * inv_a_prime) % L_prime
            if t0 > M - 1:
                cnt = 0
            else:
                cnt = ((M - 1 - t0) // L_prime) + 1
            total += x_val * cnt
        if total > max_C:
            max_C = total
    print(max_C)

if __name__ == '__main__':
    main()
0