Metropolis to Beach - NZIC 2023 Round 3 Tutorial

This problem comes from New Zealand Olympiad in Informatics (NZOI) 2023 Round 3. For the problem statement refer to here: Metropolis to Beach.

This is an easy problem, hence I’ll jump straight to the solution.

1. Algorithm

This problem basically asks you to calculate the sum of the longest consecutive positive numbers.
Hence this is my solution:

1. Initialize two variables, uphill and max_uphill:
   uphill stores the sum of consecutive positive numbers and up_hill stores the maximum one.
2. If the block is positive, add this block to uphill.
3. Else if the block is negative or we are at the end, find the maximum between uphill and max_uphill, and set up_hill to zero.
4. Return max_uphill.

2. C++ Solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;

    int block;
    int uphill = 0;
    int max_uphill = -1;
    for (int i = 0; i <= N; i++) {
        cin >> block;
        if (block > 0 and i < N) {
            uphill += block;
        } else {
            if (uphill > 0) {
                max_uphill = max(uphill, max_uphill);
                uphill = 0;
            }
        }
    }
    
    cout << max_uphill << endl;

    return 0;
}