Maximum Meat from Pig Arrivals and Departures
National Olympiad — National round (2009 season)
Submission name: pigfarm.cpp
Problem summary
Pigs weigh age² after age days. Assign each departure an already-arrived pig to maximize total meat.
Input
n, n arrival days, then n departure days.
Output
The maximum sum of squared ages.
Constraints
1 < n <100; days are positive integers below365; no arrival coincides with a departure and every departure prefix is feasible.
Worked example
Input and output for the worked example discussed below.
Input
4 10 6 1 4 5 9 8 13
Output
78
Solution analysis
- Sort both lists. Before each departure push all newly arrived pigs onto a stack in arrival order; its top is the newest available pig.
- Choose that newest pig now and leave older pigs for later. Exchanging an older-now/newer-later assignment increases or preserves weight by2(dLater−dNow)(aNew−aOld), because squared growth benefits a larger age spread.
- The sample departures5,8,9,13 take arrivals4,6,1,10, giving ages1,2,8,3 and total1+4+64+9=78. Choosing the currently heaviest pig is not optimal.
Why it works
At the first departure where an optimal schedule differs, swap its chosen pig with the newest available pig assigned later. Both were available, so feasibility is retained, and the exchange formula shows no loss. Repeating yields a greedy optimal schedule.
Watch out. Sort input dates and choose newest available rather than oldest; never use a pig that has not arrived.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
vector<int>arrivals(n);
vector<int>departures(n);
for(int&day:arrivals){
cin>>day;
}
for(int&day:departures){
cin>>day;
}
sort(arrivals.begin(),arrivals.end());
sort(departures.begin(),departures.end());
vector<int>available;
int next=0;
int answer=0;
for(int departure:departures){
while(next<n&&arrivals[next]<departure){
available.push_back(arrivals[next]);
next++;
}
// Preserve older pigs for later departures and their larger growth gain.
int age=departure-available.back();
available.pop_back();
answer+=age*age;
}
cout<<answer<<'\n';
}