1443C - The Delivery Dilemma - CodeForces Solution


binary search greedy sortings *1400

Please click on ads to support us..

Python Code:

T = int(input())
anss = []

for _ in range(T):
    n = int(input())
    dic = {}
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]
    c = [[] for i in range(n)]
    for i in range(n):
        c[i].append(a[i])
        c[i].append(b[i])
    ssum = 0
    ans = int(1e9)
    c.sort()
    for i in range(n-1,-1,-1):
        ans = min(ans , max(ssum,c[i][0]))
        ssum += c[i][1]
    anss.append(str(min(ans,ssum)))

print('\n'.join(anss))

C++ Code:

#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define ull unsigned long long int
#define PI 3.14159
#define llinf LLONG_MAX
#define inf INT_MAX
#define _inf INT_MIN
#define _llinf LLONG_MIN
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t;
    cin>>t;
    while(t--) {
        ll n;
        cin>>n;

        vector<pair<ll, ll>> v(n);

        for(int i=0; i<n; i++) {
            cin>>v[i].first;
        }

        for(int i=0; i<n; i++) {
            cin>>v[i].second;
        }


        sort(v.begin(), v.end());

        ll suff[n];
        suff[n-1] = v[n-1].second;
        for(int i=n-2; i>=0; i--) {
            suff[i] = suff[i+1] + v[i].second;
        }

        ll ans = min(suff[0], v[n-1].first);

        for(int i=n-2; i>=0; i--) {
            ll x = max(v[i].first, suff[i+1]);
            ans = min(ans, x);
        }

        cout<<ans<<"\n";
        // cout<<suff[0]<<"\n";
    }
}


Comments

Submit
0 Comments
More Questions

1301A - Three Strings
460A - Vasya and Socks
1624C - Division by Two and Permutation
1288A - Deadline
1617A - Forbidden Subsequence
914A - Perfect Squares
873D - Merge Sort
1251A - Broken Keyboard
463B - Caisa and Pylons
584A - Olesya and Rodion
799A - Carrot Cakes
1569B - Chess Tournament
1047B - Cover Points
1381B - Unmerge
1256A - Payment Without Change
908B - New Year and Buggy Bot
979A - Pizza Pizza Pizza
731A - Night at the Museum
742A - Arpa’s hard exam and Mehrdad’s naive cheat
1492A - Three swimmers
1360E - Polygon
1517D - Explorer Space
1230B - Ania and Minimizing
1201A - Important Exam
676A - Nicholas and Permutation
431A - Black Square
474B - Worms
987B - High School Become Human
1223A - CME
1658B - Marin and Anti-coprime Permutation