Submission #246270

#	Time	Username	Problem	Language	Result	Execution time	Memory
246270		SamAnd	Safety (NOI18_safety)	C++17	40 / 100	239 ms	98296 KiB

safety

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 5003, m = 5000, INF = 1000000009;

int n, h;
int a[N];
int b[200005];

int dp[N][N];

void solv()
{
    scanf("%d%d", &n, &h);

    if (n > 5000)
    {
        for (int i = 1; i <= n; ++i)
            scanf("%d", &b[i]);
        sort(b + 1, b + n + 1);
        ll ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            ans += abs(b[i] - b[n / 2 + 1]);
        }
        printf("%lld\n", ans);
        return;
    }

    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);

    for (int j = 0; j <= m; ++j)
    {
        dp[1][j] = abs(a[1] - j);
    }
    for (int i = 2; i <= n; ++i)
    {
        int k = -1;
        deque<pair<int, int> > q;
        for (int j = 0; j <= m; ++j)
        {
            while (k < min(m, j + h))
            {
                ++k;
                while (!q.empty() && dp[i - 1][k] <= q.back().fi)
                    q.pop_back();
                q.push_back(m_p(dp[i - 1][k], k));
            }
            while (q.front().se < max(0, j - h))
                q.pop_front();
            dp[i][j] = abs(a[i] - j) + q.front().fi;
        }
    }
    int ans = INF;
    for (int j = 0; j <= m; ++j)
        ans = min(ans, dp[n][j]);
    printf("%d\n", ans);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message (stderr)

safety.cpp: In function 'void solv()':
safety.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &h);
     ~~~~~^~~~~~~~~~~~~~~~
safety.cpp:26:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &b[i]);
             ~~~~~^~~~~~~~~~~~~
safety.cpp:38:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~

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