Equal from Hacker Rank

equal.cpp

/* Copyright 2017 Rafael Rendón Pablo <[email protected]> */
// region Template
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long           int64;
typedef unsigned long long  uint64;
const double kEps   = 10e-8;
const int kMax      = 50002;
const int kInf      = 1 << 30;
// endregion

int dp[kMax];

int f(int n) {
    if (n < 0) {
        return kInf;
    }
    if (n == 0) {
        return dp[n] = 0;
    }
    int& ans = dp[n];
    if (ans != -1) {
        return ans;
    }
    ans = std::min(f(n - 1), std::min(f(n - 2), f(n - 5))) + 1;
    return ans;
}

void init() {
    memset(dp, -1, sizeof dp);
    for (int i = 0; i < kMax; i++) {
        f(i);
    }
}

int solve(vector<int>& A) {
    int x = *std::min_element(A.begin(), A.end());
    int best = kInf;
    for (int v = x; v >= 0; v--) {
        bool ok = true;
        int sum = 0;
        for (int a : A) {
            int steps = dp[a-v];
            //cout << a << " - " << v << " = " << steps << endl;
            if (steps == -1) {
                ok = false;
                break;
            }
            sum += steps;
        }
        if (ok) {
            best = std::min(best, sum);
        }
    }
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    init();
    for (int tc = 1; tc <= T; tc++) {
        int n;
        cin >> n;
        vector<int> A(n);
        for (int& a : A) {
            cin >> a;
            a += 5;
        }
        cout << solve(A) << endl;
    }
    return EXIT_SUCCESS;
}