Mice
National Olympiad — Municipal round (2012 season)
Submission name: mice.cpp
Problem summary
Initially all cells of a rectangular integer grid are empty. Each delivery adds mice to a specified cell. Find the largest total number of mice in the four side-neighbours of an empty cell at the end of the day.
Source clarification. The statement bounds delivered coordinates but does not state a finite outer grid boundary. The implementation treats positive integer row and column indices as valid cells.
Input
k, followed by k triples row column count.
Output
The largest neighbouring total.
Constraints
1 ≤ k ≤ 2000; delivery coordinates 1..1000000; each delivery contains 1..1000 mice.
Worked example
Official statement sample.
Input
6 1 1 1 1 1 1 2 1 3 2 1 4 5 6 9 6 5 8
Output
17
Solution analysis
- Combine repeated deliveries in a map indexed by the coordinate pair. Only neighbours of occupied cells can have a positive neighbouring total; all other empty cells have total zero.
- For each occupied cell add its final population to the totals of its four neighbours. Skip nonpositive row or column coordinates, since cells are numbered with positive indices. Finally consider only candidate cells absent from the population map.
- In the sample the deliveries at (1,1) combine to 2 and those at (2,1) combine to 7. The empty cell (5,5) neighbours populations 9 and 8, giving the maximum 17.
Why it works
Each occupied cell contributes its mice exactly once to each side-neighbour total. Every positive-score empty cell is generated by at least one such contribution, and filtering occupied candidates enforces the empty-cell requirement. Taking the maximum is therefore exact.
Watch out. Repeated deliveries accumulate. A populated candidate is forbidden even when its neighbours have a large sum.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<map>
#include<utility>
#include<algorithm>
using namespace std;
int main(){
int k;
cin>>k;
map<pair<int,int>,int>mice,score;
while(k--){
int r,c,count;
cin>>r>>c>>count;
mice[{r,c}]+=count;
}
const int dr[]={-1,1,0,0};
const int dc[]={0,0,-1,1};
// Distribute each occupied cell to the four candidate empty cells it touches.
for(const auto&entry:mice){
for(int d=0;d<4;++d){
int r=entry.first.first+dr[d];
int c=entry.first.second+dc[d];
if(r>0&&c>0){
score[{r,c}]+=entry.second;
}
}
}
int answer=0;
for(const auto&entry:score){
if(!mice.count(entry.first)){
answer=max(answer,entry.second);
}
}
cout<<answer<<'\n';
}