PROBLEM LINK:
Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest
Setter: Ashish Vishal, Aditya Kumar Singh
Tester: Daanish Mahajan
DIFFICULTY:
Cake-Walk
PREREQUISITES:
Sorting, Greedy
PROBLEM:
Given the height of N boys and N girls in two arrays A and B. You have to form an N couple such that the maximum of the sum of the height of all couples must be minimum.
EXPLANATION:
Sort array A in increasing order and array B in decreasing order, then iterate ‘i’ from 1 to N and updating the required ans by max(ans,A[i]+B[i]).
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define is insert
#define rep1(i,a,b) for(long long i=a;i<=b;i++)
#define F first
#define S second
#define file ifstream fin("input.txt");ofstream fout("output.txt");
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fr(n) for(long long i=0;i<n;i++)
#define rep(i,a,b) for(long long i=a;i<b;i++)
#define ALL(x) (x).begin(), (x).end()
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
void solve()
{
ll n;
cin>>n;
vi a(n),b(n);
fr(n)cin>>a[i];
fr(n)cin>>b[i];
sort(ALL(a));
sort(ALL(b));
reverse(ALL(b));
fr(n)a[i]+=b[i];
ll ans=*max_element(ALL(a));
cout<<ans<<endl;
}
int32_t main()
{
#ifndef ONLINE_JUDGE
freopen("inputf.in", "r", stdin);
freopen("outputf.in", "w", stdout);
#endif
fast;
ll t=1;
cin>>t;
while(t--)
solve();
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
# define ll long long int
# define pb push_back
# define pll pair<ll, ll>
# define pli pair<ll, int>
# define mp make_pair
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
// char g = getc(fp);
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
// cout << x << " " << l << " " << r << endl;
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
// char g=getc(fp);
assert(g != -1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
const int maxn = 2e4, maxt = 5, maxv = 1e9;
int main()
{
int t = readIntLn(1, maxt);
while(t--){
int n = readIntLn(1, maxn);
vector<int> a, b;
for(int i = 0; i < n; i++)a.pb(i == n - 1 ? readIntLn(1, maxv) : readIntSp(1, maxv));
for(int i = 0; i < n; i++)b.pb(i == n - 1 ? readIntLn(1, maxv) : readIntSp(1, maxv));
sort(a.begin(), a.end());
sort(b.begin(), b.end(), greater<int>());
int ans = 0;
for(int i = 0; i < n; i++)ans = max(ans, a[i] + b[i]);
cout << ans << endl;
}
assert(getchar()==-1);
}