PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Daanish Mahajan
Testers: Shubham Anand Jain, Aryan
Editorialist: Nishank Suresh
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Given the IMDB rating (R_i) and space taken (S_i) of N movies, and the amount of free space X on Chef’s hard disk, find the highest rated movie which can fit on Chef’s disk.
EXPLANATION:
It is enough to simply implement exactly what the problem asks for.
The constraints guarantee that X\geq min (S_i), so at least one movie will fit on the disk.
Initialize an answer variable, ans = 0.
Iterate over all the N movies. For each i, if the S_i\leq X, set ans = max(ans, R_i)
At the end, ans is the required answer.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
SOLUTIONS:
Setter's Solution (C++)
#include<bits/stdc++.h>
# define pb push_back
#define pii pair<int, int>
#define mp make_pair
# define ll long long int
using namespace std;
const int maxn = 1e5, maxt = 10, minv = 1, maxv = 1e9;
int main()
{
int t; cin >> t;
while(t--){
int n, space; cin >> n >> space;
int ans = 0;
for(int i = 0; i < n; i++){
int s, r; cin >> s >> r;
if(s <= space)ans = max(ans, r);
}
assert(ans > 0);
cout << ans << endl;
}
Tester's Solution (C++)
//By TheOneYouWant
#pragma GCC optimize ("-O2")
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
int main(){
fastio;
int t;
cin>>t;
while(t--){
long long int n, x, s, r;
cin>>n>>x;
long long int ans = -1e9;
for(int i = 0; i < n; i++){
cin>>s>>r;
if(s <= x) ans = max(ans, r);
}
cout<<ans<<endl;
}
return 0;
}
Editorialist's Solution (Python)
t = int(input())
for _ in range(t):
n, x = map(int, input().split())
best = 0
for i in range(n):
space, rating = map(int, input().split())
if space <= x:
best = max(best, rating)
print(best)