Best Three Consecutive Circular Bushes
National Olympiad — Municipal round (2010 season)
Submission name: harvest.cpp
Problem summary
Bushes stand in a circle. One harvesting action collects a chosen bush and its two immediate neighbours. Find the largest total yield of an action.
Input
n followed by n yields in circular order.
Output
The largest yield collected in one action.
Constraints
3 ≤ n ≤ 1000; 0 ≤ yield ≤ 10^9.
Worked example
Input and output for the worked example discussed below.
Input
4 1 2 3 4
Output
9
Solution analysis
- Choosing the middle bush completely determines the three collected bushes. Enumerate every possible middle position; there are only n actions to compare.
- Use modular indices to wrap around: the neighbours of i are (i+n−1)%n and (i+1)%n. Read yields into a long long array because a triple can sum to 3×10^9.
- For [1,2,3,4], centering at the third bush collects 2+3+4=9, the maximum. With n=3 every action collects all three distinct bushes; the same formula still works.
Why it works
Every legal action has exactly one chosen middle bush, and the loop evaluates its exact three-bush sum. Taking the maximum over all middle positions therefore considers all possible actions and returns the optimal one.
Watch out. Do not miss triples crossing the end of the array. The answer needs 64-bit arithmetic even though a single yield fits int. Only three bushes are collected, not arbitrary separated bushes.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<cmath>
#include<iostream>
#include<limits>
#include<map>
#include<numeric>
#include<set>
#include<string>
#include<vector>
using namespace std;
int main(){
int count;
cin>>count;
vector<long long>yield(count);
for(long long&value:yield){
cin>>value;
}
long long answer=0;
for(int index=0;index<count;index++){
// Modulo joins the last bush back to the first.
long long total=yield[(index+count-1)%count]+yield[index]+yield[(index+1)%count];
answer=max(answer,total);
}
cout<<answer<<'\n';
}