Avevo provato a fare ois_fairgame durante la mirror, ma l’ho buggato, poi quando ho provato a debuggarlo non sono riuscito a capire perche’ dia WA (mi fa 50 punti coi subtask 5,6,7).
Il mio approccio: faccio una dp dove dp_i e’ il guadagno del giocatore che inizia rispetto all’altro se rimangono i sassi. quindi dp_0 = P-Q e dp_i =
-\min_{\forall k \in [i-k,i-1]} (dp_k+((i-k) \mod 2)*M) e a sto punto la soluzione dovrebbe essere dp_n, per avere il minimo fast mi tengo due minqueue (una per gli i pari, una per i dispari)
questo e’ il codice:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
ll n,k,m,p,q;
struct Mq{
queue<ll> q;
deque<ll> dq;
void push(ll x){
while(dq.size()&&dq.back()>x)dq.pop_back();
dq.push_back(x);
q.push(x);
}
ll min(){
if(!q.empty())
return dq.front();
return inf;
}
void pop(){
if(q.front()==dq.front())dq.pop_front();
q.pop();
}
};
int main(){
cin.tie(0);
ios_base::sync_with_stdio(0);
cin>>n>>k>>m>>p>>q;
Mq a[2];
a[0].push(p-q);
ll t=p-q;
for(int i=1; i<=n; ++i){
if(i>k)
a[(i&1)^(k&1)^1].pop();
t = -min(a[(i&1)^1].min()+m,a[i&1].min());
a[i&1].push(t);
}
cout<<t<<endl;
return 0;
}
Thx for the help.
, solo che non capisco perché dia 50 