goldenskygiang's blog

By goldenskygiang, 4 years ago, In English

Hello, Codeforces community!

My country is going to host an Olympiad in Mathematics, Informatics, Physics, and Russian language for admitting students who want to study in Russian universities.

I'm currently interested in studying in Moscow. Can anyone here recommend any universities that are major in Computer Science and give reviews about facilities, curriculum, tuition & accommodation fee and extra-curricular activities, especially MIPT and MPEI? Are there any universities outside Moscow that you want to recommend too?

Also, I see that the Codeforces site is sponsored by ITMO, so giving reviews about it is also helpful to me.

Full text and comments »

  • Vote: I like it
  • +14
  • Vote: I do not like it

By goldenskygiang, history, 5 years ago, In English

You're given a matrix $$$A$$$ of size $$$N * M$$$, consisting of integers satisfying $$$|A_{i,j}| \leqslant 100$$$. Rows are numbered $$$1$$$ to $$$N$$$ downward, and columns are numbered $$$1$$$ to $$$N$$$ from left to right. There are 2 players, each one will move from block $$$(1, 1)$$$ to block $$$(N, M)$$$ and can only move to the right or downward. 2 paths made by the 2 players can only have $$$(1, 1)$$$ and $$$(N, M)$$$ as two common blocks. All other blocks in the 2 paths must be distinct. Find the 2 paths that have maximum sum when combined.

Input: the first line consists of 2 numbers $$$N$$$ and $$$M$$$. $$$(N, M \leqslant 200)$$$

Next $$$N$$$ lines consist of $$$M$$$ integers describing the matrix $$$A$$$. Note that $$$A_{1,1} = A_{N,M} = 0$$$.

Output: The maximum sum of the 2 paths.

Example Input:

3 3

0 2 3

4 5 6

7 8 0

Example Output:

32

This problem was included in an offline contest that I participated yesterday. Other contestants said that this is a DP problem but I couldn't figure out the solution.

Full text and comments »

Tags dp
  • Vote: I like it
  • +1
  • Vote: I do not like it