Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Double Nesting Monte Carlo && Greedy

Revision en3, by yawn_lento, 2026-07-24 06:03:05

Title: Grid Access (NOIP 2000) Problem Description: There is an N×N grid (N≤9). Some cells contain positive integers, while others contain 0.

A person starts from the top-left cell A and walks to the bottom-right cell B. He can only move downward or rightward during the walk.

When he passes through a cell, he takes the number in that cell (the number becomes 0 after being taken).

Now, this person needs to walk from A to B twice. Find the maximum possible sum of the numbers taken from the two paths.

Input Format: The first line contains a single integer N, representing the size of the grid. The following lines contain triples of integers x,y,v, where v is the integer placed in the cell at row x and column y.

The input is terminated by a single line containing 0 0 0.

Output Format: Output a single integer, representing the maximum total sum of the numbers collected on the two paths.

Sample Input:

8 2 3 13 2 6 6 3 5 7 4 4 14 5 2 21 5 6 4 6 3 15 7 2 14 0 0 0

Sample Output:

67

Constraints:

1≤N≤9,1≤x,y≤N,1≤v≤30

Using two layer of Monte Carlo and Greey algorithm, I managed to gain AC, though still achievable at small numbers.

below are my codes in Github:

https://github.com/yawn-lento/yawn-s-codes/blob/main/P1004%20%E5%8F%8C%E5%B1%82%E9%9A%8F%E6%9C%BA%E5%B5%8C%E5%A5%97%E5%B0%9D%E8%AF%95.cpp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English yawn_lento 2026-07-24 06:03:05 8 Tiny change: ' Output:\n\n67\nCons' -> ' Output:\n67\nCons'
en2 English yawn_lento 2026-07-24 06:01:56 1072 Tiny change: 'in Github:https://gi' -> 'in Github:\n\nhttps://gi'
en1 English yawn_lento 2026-07-24 05:57:03 322 Initial revision (published)