Square869120Contest #5 will be held on Sunday, April 15th, 20:00 JST.

**About Square869120Contest**

- This contest is unofficial.
- Square869120Contest has been held 4 times before, and this is the 5-th contest of Square869120Contest.
- From the 3-rd contest,
**both Engish and Japanese statements are prepared.**

**Contest Information**

- Time: Sunday, April 15th, 20:00 JST
- Duration: 240 minutes
- Tasks: 9 (Consists of 8 algorithm tasks, 1 marathon task)
- Writer: E869120, square1001
- Rated: No (unrated)
**The first problem is as easy as Codeforces Div2 A, and the last problem is as hard as Codeforces Div1-D,E problems. In addition, there are many partial scores. I think all participants can enjoy the contest.**

**Scoring**

Task ID | Max Score | Partial Scores |
---|---|---|

A | 200 | 100+100 |

B | 300 | 70+140+90 |

C | 500 | 90+100+310 |

D | 600 | 120+160+320 |

E | 800 | 40+160+190+410 |

F | 1000 | 60+60+250+630 |

G | 1200 | 80+320+[0 ----- 800, 1-point unit] |

H | 1400 | 210+320+870 |

I | 1500 | Marathon Task, 1-point unit |

**Past Contests**

Square869120Contest is one of the unrated contest which have a long history. There's 4 previous contest, so you can solve them to practice this kind of contest.

- Square869120Contest #4 (English / Japanese)
- Square869120Contest #3 (English / Japanese)
- Square869120Contest #2 (Japanese)
- Square869120Contest #1 (Japanese)

**Updates**

1. Some of the partial scores has changed. Please check.

2. Some of the partial scores has changed. We think the point values are determined.

3. The contest is over. Thank you for your participation!

4. English editorial will be published on Thursday, 4/19/2018.

5.

**English editorial uploaded. Link**

**We are looking forward to your participation! Let's participate and enjoy!!!!!**

Will there be english analysis?

This time we'll put some effort to make an English editorial (at least brief full-score solution explanation of problems except problem I).

Hmmm there is no English Editorial ...

Look "Updates" in the announcement blog. The English editorial will be published on Thursday, 4/19/2018.

[Reminder] The contest will start in 3 hours.How to solve problem "Lunch Menu"?

I solved it with DP.

Now we consider array a[1...n] and we know the position p such that a[p] = max(a[1...n]).

We can:

Not erase position p:

In this case, every queries have l(i) <= p <= r(i) will pick p, so the total cost = "number of queries such that l(i) <= p <= r(i)" * a[p].

After that, we can skip queries that have l(i) <= p <= r(i) so we can split array [1...n] to array [1...p-1] and [p+1...n].

With that observation we can think about DP with f(l, r, ...).

Erase position p:

We can store variable lim so that next time we only consider position i such that a(i) < lim.

We can compress array so lim <= n.

After merging 2 cases, we can know which states we need to store.

So DP will look like f(l, r, number of elements we can erase, limit).

DP transtion tooks O(N). So total complexity is O(N ^ 5).

My code: https://pastebin.com/iczqhRcZ.

Awesome solution.

The complete English editorial of this contest uploaded.Thank you for your participation!

Link to Editorial