This was the second problem I attempted, I expected to solve it in 15 mins and I made the first submission at 12minuts but wrong answer, it took me another 10 mins to debug.
It looks a lot like a DP, but $p$ is too large, since “simple problems” contribute $0$ to the answer, a greedy idea is that none of the solutions should contain any “simple problem”.
Obviously, the function of solving time and the number of problems solved is monotonic. Use binary search to find the number of problems solved. $O(n\log^2)$
There’s a more elegant global greedy approach. First sort all problems with the first key as difficulty in descending order, and the second key as score in ascending order. Maintain a priority queue and the current minimum difficulty of all problems. Each time pop the problem with the longest time from the queue, then insert other problems into the queue. The condition is that the difficulty of the problem must be $\geq$ the minimum difficulty in the priority queue. $O(n\log)$
Previously I used to write a separate function for verifying the answer in binary search. This time, in a rush, I wrote it together with the main function, leanding to a typo while updating the answer. It took me 10mins to find the issue:(
// compile: make data
// run: ./data < data.in
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#ifdef LOCAL
#include <debug/codeforces.h>
#define debug(x...) _debug_print(#x, x);
#define Debug(x...) _debug_print_format(#x, x);
std::ifstream terminal("/dev/tty");
#define PP cerr<<"\033[1;30mpause...\e[0m",terminal.ignore();
#else
#define debug(x...)
#define Debug(x...)
#define PP
#endif
template<typename...Args> void print_(Args...args){((cout<<args<<" "),...)<<endl;}
#define rep(i,a,b) for(int i=(a);i<(int)(b);++i)
#define sz(v) ((int)(v).size())
#define print(...) print_(__VA_ARGS__);
#define FIND(a, x) ((find(a.begin(),a.end(),(x))!=a.end())?1:0)
#define cmin(x,...) x=min({(x),__VA_ARGS__})
#define cmax(x,...) x=max({(x),__VA_ARGS__})
#define INTMAX (int)(9223372036854775807)
#define INF (int)(1152921504606846976)
#define NaN (int)(0x8b88e1d0595d51d1)
#define double long double
#define int long long
#define uint unsigned long long
#define MAXN 200010
int32_t main() {
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, m; cin >> n >> m;
vector<pair<int, int>> a(n);
vector<int> f;
rep(i, 0, n) cin >> a[i].first >> a[i].second;
int L = 0, R = n;
int ans = 0;
while (L <= R) {
int mid = (L + R) >> 1;
vector<pair<int, int>> v;
rep(i, 0, n) if (a[i].first >= mid) v.push_back({a[i].second, i});
bool valid = 0;
vector<int> tmp;
if (sz(v) >= mid) {
sort(v.begin(), v.end());
int t = 0;
rep(i, 0, mid) {
t += v[i].first;
tmp.push_back(v[i].second);
}
valid = t <= m;
}
if (valid) {
ans = mid;
f = tmp;
L = mid + 1;
}
else R = mid - 1;
}
cout << ans << endl << ans << endl;
rep(i, 0, sz(f)) cout << f[i]+1 << " \n"[i==sz(f)-1];
return 0;
}
WinPH777LoginPhilippines is perfect for local players! Easy deposit options and a wide range of games. Try your luck kabayan! winph777loginphilippines
Was hesitant to try loab52.com at first, but glad I did. The community is active, and the games are fun. A good place to waste a bit of time I’ll be honest. Have a look right here loab52.
Considering using tt88bet. How easy is it to navigate? I don’t want to spend hours trying to find the games I want!
Anyone else playing on sv388 online borneo303? I’ve had some decent luck on the cockfights. Let me know your strategies!
Clover 999 sounds lucky as heck! I need some of that four-leaf clover charm in my life. Gonna give it a try on phspin77, hopefully I hit the jackpot dude! clover 999
Need that Casino Plus app for my Android ASAP! Hope it runs smooth and doesn’t drain my battery. Let’s roll! Android download here: casino plus app download for android
It’s fascinating how easily we fall into patterns when gambling – chasing losses is a classic! Seeing platforms like 6win offer quick deposits (even via GCash!) might increase that impulse, so awareness is key. Responsible gaming first! 🤔
Feeling that calm at the table is key, and Go Perya’s security lets you focus on strategy. Check out go perya slot download for licensed games with verified payments and strong KYC protection.
The shift from $O(n\log^2)$ to $O(n\log)$ perfectly illustrates how optimizing the underlying process can drastically change the outcome. This principle of maximizing return on limited resources applies everywhere, from supply chain logistics to finding the best platform for structured entertainment, like at the n777 online casino. Efficiency is the ultimate goal, regardless of the domain.
Casino Plus offers verified RTPs from 92% to 98.5%, but volatility matters most; explore their math models at casino plus before chasing high-stakes action on slots or live tables today.
Dude, the RTP transparency thing is actually kinda wild. Knowing the actual math behind it, like the slot RTP range, is a huge upgrade. Check out Okey Plus slot; it’s way deeper than just spinning!
The VIP focus mentioned is key; it suggests robust backend integration. For deeper analysis on platform security, check out love ph com. Understanding the underlying RNG models is always the next step for true optimization.
The platform’s diverse offerings are solid, but analyzing the underlying probability distributions across slots is where the real fun begins. Check out jl95 vip for more deep dives!
Reading about game theory really highlights how much psychology impacts play. Seeing platforms like phfun prioritize a smooth, secure experience – like their quick registration – builds player trust, crucial for long-term strategy. It’s all connected!
[8067]Wazobet Official Login | Best GCash Online Casino Philippines,Wazobet offers a seamless app download for the best slots real money experience. Enjoy secure GCash payments and easy baccarat guides. Join the action now! visit: wazobet
The graphics are amazing and the gameplay is very smooth. I really enjoy the variety of themes they have available here. xgjili777
The platform overview is helpful, but remember that glossy ‘rewards’ rarely tell the whole story. Always cross-reference the fine print regarding withdrawals and terms. For a solid starting point, check out this t71 player guide before committing funds. Safety first!
[3270]Tribun855: Login Daftar Slot Gacor Deposit Dana Terpercaya,Tribun855 menyediakan akses login dan daftar mudah untuk main slot gacor deposit dana serta baccarat online. Download apk casino terpercaya sekarang juga. visit: tribun855
The UI flow for new users seems slick; mastering the deposit process is key. For deeper insights on platform usability, check out ph947 online casino. Great read!
Honestly, the focus on ‘cân bằng’ in the description is refreshing. Most sites ignore the mindset. Still, always check your bankroll first, regardless of how good the 79 club game looks. Discipline > Jackpot, always.
Best experience so far in the PH region. The graphics are sharp and the gameplay is fair. I am definitely sticking with phswertewin from now on.
I’ve tried a few platforms recently but this one is surprisingly smooth. The interface is intuitive and the payouts are fast. Definitely recommend checking out vnggk88 if you are looking for a reliable spot.
Just found this gem between classes! The 24/7 support sounds legit for Baccarat fans. Check out Table Games Casino com to join the action now, guys!
Finally found a site that does not lag during the big wins. The interface is very user friendly and the payouts are legit. Love jili188login so much!
Honestly the best experience I have had with slots recently. The payouts are fair and the interface is super smooth. Check out phggjili for a great time.
The focus on a seamless, high-performance environment is key. Beyond the buzz, understanding the core mechanics is what matters. Check out 222jl download apk for a solid look at their tech stack.
Hmm, analyzing the odds here is tricky. The sheer variety mentioned for 3333 bet apk গেমস is impressive, but remember, pure math dictates the house edge. Gotta balance the fun with reality!