nkq18072008's blog

By nkq18072008, history, 2 months ago, In English

Given a sequence of n integers a1, a2, ..., an and an integer k. The degree of beauty of a subsequence consecutive ai, ai+1, …, aj are evaluated by GCD(ai, ai+1, …, aj).(ai + ai+1 + … + aj), i.e. beauty is equal to the greatest common divisor of the elements in the subsequence multiplied by the sum of the parts element in that subsequence. Requirement: Find a consecutive subsequence with at least k elements and with the greatest degree of beauty. Input from the text file BSEQUENCE.INP - Line 1: Two integers n, k (1 ≤ k ≤ n ≤ 106 ); - Line 2: n integers a1, a2, …, an (1 ≤ ai ≤ 106 ). Ouput writes to the text file BSEQUENCE.OUT a single integer that is the level of beauty found. Example: Input: 6 2 4 4 4 3 1 3 Output: 48 Subtasks: • 10% of the points correspond to 10% of the tests with n, k ≤ 100; • 20% of the points correspond to 20% of the tests with n, k ≤ 5000; • 25% of the points correspond to 25% of the tests with anyone ≤ 100; • 20% of points corresponds to 20% of tests with n, k ≤ 5,104 ; • 25% of the points correspond to 25% of the tests without any additional constraints

  • Vote: I like it
  • -5
  • Vote: I do not like it