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

Double Nesting Monte Carlo && Greedy
Difference between en2 and en3, changed 8 character(s)
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)