COCI '14 Contest 7 #3 ACM

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem types

The team of the University of Zagreb - Stjepan, Ivan and Gustav — are taking part in the World Finals of the ACM International Collegiate Programming Contest in Morocco. Their technical guide Goran has come up with an invincible strategy to use for solving tasks in the finals.

In the very beginning, each team member quickly estimates the difficulty of each of the N tasks. The difficulties are described by numbers from 1 to 5, and their meaning is the following:

  • 1 - hehehe
  • 2 - bring it on!
  • 3 - well OK.
  • 4 - hmmmm…
  • 5 - are you insane?

After this, they will distribute the tasks between them. For simplicity's sake, this array of tasks will be split into three parts so that each team member gets a nonempty array of consecutive tasks to contemplate about. The distribution is made so that the sum of estimated difficulties is minimal, whereas only the estimates of the team members whom that task is assigned to is calculated. Your task is to calculate that minimal possible sum.


The first line of input contains the integer N (3 \le N \le 150\,000), the number of tasks.

Each of the following three lines contains N integers (from 1 to 5): the estimated task difficulties, give respectively. First of those lines corresponds to Stjepan's estimates, the second to Ivan's and the third to Gustav's.


The first and only line of output must contain the minimum sum of difficulties.

Sample Input 1

1 3 3
1 1 1
1 2 3

Sample Output 1


Sample Input 2

3 3 4 1 3 4 4
4 2 5 1 5 5 4
5 5 1 3 4 4 4

Sample Output 2


Clarification of the first example: Stjepan gets the first, Gustav the second and Ivan the third task.

Original PDF


  • 8
    kobortor  commented on Nov. 30, 2015, 5:11 p.m.

    Formatting slightly different because technical stuff.

    Please be patient the other COCI problems are coming soon^{tm}\(None\)

    • 2
      cheesecake  commented on Nov. 30, 2015, 5:28 p.m.

      Thanks for the initiative!