제출 #1280698

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280698		ionut27	Rabbit Carrot (LMIO19_triusis)	C++20	14 / 100	1103 ms	177304 KiB

triusis

#include "bits/stdc++.h"
#include <type_traits>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

// ============ Macros starts here ============
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif // DEBUG
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream, ostream>::value, Ostream&>::type operator<<(Ostream& os, const Cont& v) {
    os << "[";
    for (auto& x : v) { os << x << ", "; }
    return os << "]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p) {
    return os << "{" << p.first << ", " << p.second << "}";
}

#define readFast                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
#ifdef LOCAL
#define read() ifstream fin("date.in.txt")
#else
#define read() readFast
#endif // LOCAL
// ============ Macros ends here ============

#define fin cin
#define ll long long
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define output(x) (((int)(x) && cout << "YES\n") || cout << "NO\n")
#define LSB(x) (x & (-x))
#define test cout << "WORKS\n";

const int N = 2e5 + 15;
const int MOD = 998244353;

int n, k;
int a[N];
unordered_map<int, unordered_map<int, int>> cache;

int solve(int j, ll hAct) {
    if (j == n + 1) {
        return 0;
    }
    if (cache.find(j) != cache.end() && cache[j].find(hAct) != cache[j].end()) {
        return cache[j][hAct];
    }

    int ans = min(solve(j + 1, hAct + k), solve(j + 1, max(hAct - k, 0ll))) + 1;

    if (hAct + k >= a[j]) {
        ans = min(ans, solve(j + 1, a[j]));
    }
    return cache[j][hAct] = ans;
}

int main() {
    read();

    fin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        fin >> a[i];
    }
    // fill(cache, cache + N, -1);
    cout << solve(1, 0);

    // vector<vector<int>> dp(n + 1, vector<int>(3, INT_MAX));
    // dp[0][0] = 0;
    // for (int i = 1; i <= n; ++i) {
    //     // 0 - no change
    //     if (a[i - 1] + k >= a[i]) {
    //         dp[i][0] = min({ dp[i - 1][0], dp[i - 1][1], dp[i - 1][2] });
    //     }
    //     // 1 - increase
    //     else {
    //         dp[i][1]
    //     }

    // }

    return 0;
} /*stuff you should look for !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   * test the solution with the given example
   * int overflow, array bounds, matrix bounds
   * special cases (n=1?)
   * do smth instead of nothing and stay organized
   * WRITE STUFF DOWN
   * DON'T GET STUCK ON ONE APPROACH
~Benq~*/

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