Submission #1174431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174431		ezzzay	Rabbit Carrot (LMIO19_triusis)	C++20	0 / 100	1104 ms	196680 KiB

triusis

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define int long long
const int N=5005;
vector<int>ans;
int a[N];
int dp[N][N];
signed main(){
   
   int n,x;
   cin>>n>>x;
   set<int>st={0};
   for(int i=0;i<N;i++){
       for(int j=0;j<N;j++){
           dp[i][j]=1e9;
       }
   }
   for(int i=1;i<=n;i++){
       cin>>a[i];
       st.insert(a[i]);
   }
   vector<int>v;
   for(auto a:st)v.pb(a);
   map<int,int>mp;
   
   dp[0][0]=0;
   for(int i=1;i<=n;i++){
       for(int j=0;j<v.size();j++){
           for(int k=0;k<v.size();k++){
               if(v[j]<=v[k] or (v[j]-v[k])<=x){
                   dp[i][j]=min(dp[i][j], (int)dp[i-1][k]+ (v[j]!=a[i]));
               }
           }
       }
       
    //   vector<int>tmp(N+1);
    //   tmp[N]=1e9;
    //   for(int j=N-1;j>=0;j--){
    //       tmp[j]=min(tmp[j+1],dp[j]);
    //   }
    //   for(int j=0;j<N;j++){
    //       int l= max(0ll,j-x);
    //       dp[j]= tmp[l]+(a[i]!=j);
    //   }
   }
    int ans=1e9;
    for(int i=0;i<v.size();i++){
        ans=min(ans,dp[n][i]);
    }
    cout<<ans;
}

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