結果

問題 No.1977 Extracting at Constant Intervals
ユーザー lam6er
提出日時 2025-04-16 00:10:25
言語 PyPy3
(7.3.15)
結果
MLE  
実行時間 -
コード長 1,774 bytes
コンパイル時間 462 ms
コンパイル使用メモリ 82,240 KB
実行使用メモリ 848,632 KB
最終ジャッジ日時 2025-04-16 00:11:43
合計ジャッジ時間 8,327 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

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]))
    
    g = math.gcd(N, L)
    L_prime = L // g
    N_prime = N // g
    
    # Compute modular inverse of N_prime modulo L_prime
    def modinv(a, m):
        g, x, y = extended_gcd(a, m)
        if g != 1:
            return None  # inverse doesn't exist
        else:
            return x % m
    
    def extended_gcd(a, b):
        if a == 0:
            return (b, 0, 1)
        else:
            g, y, x = extended_gcd(b % a, a)
            return (g, x - (b // a) * y, y)
    
    inv_N = modinv(N_prime, L_prime)
    if inv_N is None:
        # This should not happen since N_prime and L_prime are coprime
        print(0)
        return
    
    # Precompute cnt array
    cnt = [0] * L
    for c in range(L):
        if c % g != 0:
            cnt[c] = 0
        else:
            k = c // g
            m0 = (k * inv_N) % L_prime
            if m0 >= M:
                cnt[c] = 0
            else:
                count = (M - 1 - m0) // L_prime + 1
                cnt[c] = count
    
    # Compute S array
    S = [0] * L
    for k in range(N):
        pos = (k + 1) % L  # since positions are 1-based
        if pos == 0:
            pos = L
        S[pos - 1] += A[k]  # S is 0-based
    
    max_C = -float('inf')
    for i in range(1, L + 1):
        current = 0
        for d in range(L):
            c = (i - (d + 1)) % L  # because d is 0-based in S, but represents (d+1) mod L
            current += S[d] * cnt[c]
        if current > max_C:
            max_C = current
    print(max_C)

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