Submission #1255926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255926		_unknown_2010	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	150 ms	196600 KiB

triusis

//#ifndef khos
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#ifdef khos
    #include "t_debug.cpp"
#else
    #define debug(...) 42
#endif
using namespace std;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using indexed_multiset = tree<pair<int,int>, null_type, less<pair<int,int>>, rb_tree_tag, tree_order_statistics_node_update>;

#define int int64_t
#define vi vector
#define ss second
#define ff first
#define TESTCASES
#define all(x) (x).begin(), (x).end()
const int mod = 1e9+7;
const int MAXN=2000000+5;
const int inf=1e18;
void solution() {
    int n,m;
    cin >> n >> m;
    vi<int> a(n+1);
    for(int i=1; i<=n; i++)cin >> a[i];
    vi<vi<int>> dp(n+1, vi<int> (5005, inf));
    dp[0][0]=1;
    for(int i=0; i<n; i++){
        for(int j=0; j<=5000; j++){
            if(a[i]-j<=m){
                dp[i+1][a[i]]=min(dp[i+1][a[i]],dp[i][j]);
            }
            int val=min(j+m,(int)5000);
            dp[i+1][val]=min(dp[i+1][val], dp[i][j]+1);
        }
    }
    int mn=inf;
    for(int i=0; i<=5000; i++){
        mn=min(mn,dp[n][i]);
    }
    cout << mn;
}
int32_t main(){
    clock_t tStart = clock();
    // freopen("cowjog.in", "r", stdin);
    // freopen("cowjog.out", "w", stdout);
    #ifdef khos
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q = 1;
    #ifdef TESTCASES
        // cin >> q;
    #endif
    while(q--) {
        solution();
        cout << '\n';
    }
    cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}

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