RGPC '18 P4 - Higgs

View as PDF

Submit solution


Points: 15 (partial)
Time limit: 1.4s
Memory limit: 128M

Author:
Problem type

Rin is conducting an experiment with some particles. Her particles are numbered from 1 to N, and each has a spin value S_i. She observes her system of particles for T time "ticks", and numbers the first tick t_1. For each tick, she decides on three integers a, b, and k, which she then uses to advance her experiment in one of two ways:

  1. If the tick is prime-numbered (i.e. t_i, where i is prime), she finds the sum of the spin values between particles a and b inclusive, and then adds k to that sum. She then calls the resulting number the inefficiency E_i of the system at tick t_i.
  2. Otherwise, she increases the spins of each particle from a to b inclusive by k.

Rin defines the cost of stopping the experiment at tick t_p to be C_p = pE_p, where p is prime (i.e., the cost is a tradeoff between the final inefficiency of the system and how many ticks it takes to get there). Help her find the minimum cost.

Note: to recall, a prime number is any natural number greater than 1 that has exactly two distinct factors.

Input Specification

The first line of input consists of two space-separated integers N and T. The next line will contain N space-separated integers, indicating the spins S_i of the ith particle. T lines follow, each containing three space-separated integers a, b, and k.

Constraints

For all subtasks:

0 \le S_i \le 1\,000

1 \le a, b \le N

-1\,000 \le k \le 1\,000

Subtask 1 [20%]

1 \le N \le 10\,000

2 \le T \le 20\,000

Subtask 2 [80%]

1 \le N \le 10^6

2 \le T \le 10^5

Output Specification

Output a single integer, the minimum cost of the experiment \min_{p \le N} pE_p, for a prime p.

Sample Input 1

6 4
162 840 327 543 957 582
5 5 329
3 5 -618
5 5 -242
2 5 -173

Sample Output 1

3076

Explanation

Rin achieves the minimum cost by stopping the experiment after the 2nd tick, when the inefficiency is 1\,538.

Sample Input 2

7 5
478 186 954 257 126 420 492
2 4 104
6 7 -63
5 6 619
1 5 -704
7 7 818

Sample Output 2

1698

Comments