Submission #1229091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1229091		buixuia	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	2 ms	4424 KiB

triusis

#include<bits/stdc++.h>
using namespace std;
int n,m,a[105],v[105][10005];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i = 1; i <= n; i++) cin>>a[i];
    memset(v, -1, sizeof(v));
    queue<tuple<int,int,int>> q;
    q.push({0, 0, 0});
    v[0][0] = 0;
    while(q.size()){
        auto [p, h, c] = q.front();
        q.pop();
        if(p == n){
            cout<<c<<'\n';
            return 0;
        }
        int nx = p + 1, t = a[nx];
        if(t - h <= m){
            if(v[nx][t] == -1 || v[nx][t] > c){
                v[nx][t] = c;
                q.push({nx, t, c});
            }
        }
        else{
            int nh = h + m;
            if(v[p][nh] == -1 || v[p][nh] > c + 1){
                v[p][nh] = c + 1;
                q.push({p, nh, c + 1});
            }
            if(v[nx][nh] == -1 || v[nx][nh] > c + 1){
                v[nx][nh] = c + 1;
                q.push({nx, nh, c + 1});
            }
        }
    }
    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37