PROBLEM LINK: COLLEGE FAIR | CodeChef
Problem Code: COLLEGE FAIR | CodeChef
Practice: CodeChef | Competitive Programming | Participate & Learn | CodeChef
Contest : Carnival Finale Coding Competition | CodeChef
Author: Codechef Adgitm Chapter : naqeeb2710 | CodeChef User Profile for NAQEEB AHMED | CodeChef
Tester: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Editorialist: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
DIFFICULTY:
Easy
PROBLEM:
There is going to be a major fair in your college in which there are many events are going to happen. There are n numbers of events you can attend. You know its starting and ending days and the amount of money you could win in the event. But the condition is that you can attend only one event in a day. Tell the maximum amount of money you will win.
EXPLANATION:
Solve using map.
SOLUTION:
C++:
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
map<int,int> compress;
vector a(n),b(n),p(n);
for (int i = 0; i < n; i++) {
cin >> a[i] >> b[i] >> p[i];
b[i]++;
compress[a[i]], compress[b[i]];
}
int coords = 0;
for (auto&v : compress) {
v.second = coords++;
}
vector<vector<pair<int,int>>> project(coords);
for (int i = 0; i < n; i++) {
project[ compress[b[i]] ].emplace_back( compress[a[i]], p[i] );
}
vector dp(coords, 0);
for (int i = 0; i < coords; i++) {
if (i > 0) {
dp[i] = dp[i-1];
}
for (auto p : project[i]) {
dp[i] = max(dp[i], dp[p.first]+p.second);
}
}
cout << dp[coords-1] << endl;
}