Problem Info
2017 Open Contest, Silver, Problem 1, Paired Up
My Work
#include
#include
#include
using namespace std;
typedef long long ll;
int main(){
freopen(“pairup.in”,“r”,stdin);
freopen(“pairup.out”,“w”,stdout);
int n;
cin >> n;
vector<pair<ll,ll>> cows; //time, number
ll in1, in2;
ll total = 0;
ll count = 0;
ll bpos = n-1;
ll tmax = -1;
for(int x=0; x<n; x++){
cin >> in1 >> in2;
total += in1;
cows.push_back({in2,in1});
}
ll br = cows[n-1].second;
sort(cows.begin(),cows.end());
for(int x=0; x<n; x++){
if(count+cows[x].second<=(total/2)){
count += cows[x].second;
ll y = cows[x].second;
while(y>0){
tmax = max(tmax,cows[x].first+cows[bpos].first);
if(y>=br){
y -= br;
bpos--;
br = cows[bpos].second;
}
else{
br -= y;
y = 0;
}
tmax = max(tmax,cows[x].first+cows[bpos].first);
}
}
else{
ll y = (total/2)-count;
while(y>0){
tmax = max(tmax,cows[x].first+cows[bpos].first);
if(y>=br){
y -= br;
bpos--;
br = cows[bpos].second;
}
else{
br -= y;
y = 0;
}
tmax = max(tmax,cows[x].first+cows[bpos].first);
}
break;
}
}
cout << tmax;
}
What I’ve Tried
I made several small changes to the code. I have tried out several of my own test cases and they work fine. However, this code only works for case 1,5,7. For case 2, it gave a number less than the correct answer.