📝 문제 정보#
🧐 관찰 및 접근#
- 한 문제당 광기는 $KT$만큼 쌓이고, 해결했을때 $\text{min}(KT, 5K)$만큼 빠지므로 $T \leq 5$라면 문제를 푸는데 광기가 안쌓인다.
- 어라? 아니네. $KT \leq L$ 조건도 필요하다.
- 아 이건 문제조건에 있네.
- 암튼 이 친구들은 어차피 T시간 걸려서 풀기만 하면 상관이 없다.
- 어라? 아니네. $KT \leq L$ 조건도 필요하다.
- 나머지 문제들에 대해, 어차피 문제를 풀어서 쌓이는 광기의 합은 일정하다.
- 그러니까, 문제를 해결해서 광기를 줄이는걸 힘내야하지 않을까?
- 그러면 광기를 많이 해소할 수 있는 문제를 먼저 풀어야하는 거 같은데…
💻 풀이#
- 코드 (C++):
void solve(){
ll N, L; cin >> N >> L;
vector<pll> v;
ll ans = 0;
rep(i, 0, N){
ll K, T; cin >> K >> T;
ans += T;
if(T <= 5) continue;
v.push_back({K, T});
}
sort(all(v), [](pll a, pll b){
return min(a.first * a.second, 5 * a.first) > min(b.first * b.second, 5 * b.first);
});
ll cur = 0;
for(auto [K, T]: v){
if(cur + K*T > L){
ll rest = cur + K*T - L;
ans += rest;
cur -= rest;
}
cur += K*T;
cur -= min(K*T, 5*K);
}
cout << ans;
}