965D Single-use Stones
The problem can be found here
My Thought Process
First of all, we can see that the frogs on the starting side can jump to all the rocks within $w$ units. We should always put the frogs in the first $w$ rocks if available because the frogs in the front wouldn’t be affected by frogs behind it.
Now, the frogs should jump as far as possible because we want to waste the least number of rocks. For example, if a frog can jump 5 units and its at a distance of 1, it should jump to a distance of 6 instead of 5 if available.
Also, if a frog is further back than another frog, we should move that frog first if we can since we end up with one frog in the same distance from the target side but in addition, another frog thats closer.
Then, we just need to implement this. There is a few ways but I decide to use a deque. I iterated from a distance of 0 to a distance of n (the other side) and everytime I see an avaliable rock I try to use the frogs at the back.
Implementation
#include <bits/stdc++.h>
using ll = long long;
#define pb push_back
using namespace std;
const int MOD = 1e9+7;
const int MAXN = 2e6+1;
void solve() {
int n, k;
cin >> n >> k;
vector<int> v(n);
for(int i = 1; i < n; ++i){cin >> v[i];}
v.pb(2e9);
deque<pair<int, int>> q;
q.pb({2e9, 0});
for(int i = 1; i < n; ++i){
while(!q.empty() && v[i] > 0){
if(q.front().second == i){break;}
if(q.front().second + k < i){
q.pop_front();
continue;
}
if(q.front().first > v[i]){
q.front().first -= v[i];
q.push_back({v[i], i});
v[i] = 0;
}
else{
v[i] -= q.front().first;
q.push_back({q.front().first, i});
q.pop_front();
}
}
}
int ans = 0;
while(!q.empty()){
if(q.back().second != 0){
ans += q.back().first;
}
q.pop_back();
}
cout << ans << endl;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
solve();
return 0;
}
Final Thoughts
This was a pretty fun problem. It was quite straightforward but I do always like these type of problems that uses deques/queues/stacks. There are also many, many different ways to solve this problem. The editorial uses binary search and there’s is also a DP solution to it in the comments.
See here for the solution and another implementation.