Submission #1173870

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173870		ezzzay	Collecting Mushrooms (NOI18_collectmushrooms)	C++20	0 / 100	73 ms	328 KiB

mushrooms

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define int long long
#define ss second
#define pb push_back
const int N=555;
int dp[N];
int a[N];
int tmp[N];
int find(int l, int r){
    int h=1e14;
    for(int i=l;i<=r;i++){
        h=min(h,tmp[i]);
    }
    return h;
}
signed main(){
    int n,h;
    cin>>n>>h;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=0;i<N;i++){
        dp[i]=1e15;
    }
    for(int i=0;i<N;i++){
        dp[i]=abs(a[1]-i);
    }
    for(int i=2;i<=n;i++){
        for(int j=0;j<N;j++)tmp[j]=dp[j];
        for(int j=0;j<N;j++){
            int r=max(0ll, min(j+h,N-1));
            int l=min(N-1,max(0ll,j-h));
            dp[j]=find(l,r)+abs(j-a[i]);
        }
    }
    int ans=1e15;
    for(int i=0;i<N;i++){
        ans=min(ans,dp[i]);
    }
    cout<<ans;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 10
• Subtask 3: 0 / 18
• Subtask 4: 0 / 23
• Subtask 5: 0 / 19
• Subtask 6: 0 / 21