Submission #355368

#	Time	Username	Problem	Language	Result	Execution time	Memory
355368		gratus907	Safety (NOI18_safety)	C++17	13 / 100	2065 ms	203500 KiB

safety

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;

const int MN = 5050;
int N, H;
int s[MN];
int dp[MN][MN]; // (1-i)th, h[n] = j
int32_t main()
{
    usecppio
    cin >> N >> H;
    memset(dp, 0x7f, sizeof(dp));
    memset(dp[0], 0, sizeof(dp[0]));
    int MH = 0;
    for (int i = 1; i <= N; i++)
    {
        cin >> s[i];
        MH = max(MH, s[i]);
    }
    for (int i = 1; i <= N; i++)
    {
        for (int j = 0; j <= MH; j++)
        {
            int lb = max(j - H, 0);
            int ub = min(j + H, MH);
            for (int lst = lb; lst <= ub; lst++)
                dp[i][j] = min(dp[i-1][lst] + abs(j - s[i]), dp[i][j]);
        }
    }
    int ans = dp[N][0];
    for (int i = 1; i <= MH; i++)
        ans = min(dp[N][i], ans);
    cout << ans << '\n';
}

• Subtask 1: 3 / 3
• Subtask 2: 4 / 4
• Subtask 3: 0 / 9
• Subtask 4: 0 / 5
• Subtask 5: 6 / 6
• Subtask 6: 0 / 11
• Subtask 7: 0 / 11
• Subtask 8: 0 / 22
• Subtask 9: 0 / 29