Submission #1230380

#TimeUsernameProblemLanguageResultExecution timeMemory
1230380free_de_la_zenithRabbit Carrot (LMIO19_triusis)C++20
0 / 100
38 ms1864 KiB
/** * author: MINHTPC * **/ #include <bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define all(a) a.begin() , a.end() #define FOR(i ,a , b) for(int i = a ; i <= b ; ++i) #define bit(mask,i) ((mask>>i)&1) #define name "task" #define lo lower_bound #define up upper_bound #define count_bit1(x) __builtin_popcountll(x) #define count_bit01(x) __builtin_clzll(x) #define count_bit10(x) __builtin_ctzll(x) using namespace std; const int N=2e5+5; long long a[N],n,k; namespace sub1 { int ch[N]; const int INF=1e9; void solve() { for(int i=0;i<n;i++) cin >> a[i]; int ans=INF; for(int mask=0;mask<(1<<n);mask++) { int len=__builtin_popcount(mask); for(int i=0;i<n;i++) if(bit(mask,i)) ch[i]=1; int ok=0; for(int i=1;i<n;i++) { if(a[i]-a[i-1]>k) { if(!ch[i]) { ok=1; break; } } } if(!ok) { ans=min(ans,len); } } cout << ans; } } namespace sub23 { const long long INF=-1e18; long long dp[N]; void solve() { for(int i=1;i<=n;i++) cin >> a[i]; fill(dp,dp+N,INF); long long ans=0; for(int i=1;i<=n;i++) { if(a[i]<=k*i) dp[i]=1; for(int j=1;j<i;j++) { if(dp[j] && a[i]-a[j]<=k*(i-j)) dp[i]=max(dp[i],dp[j]+1); } ans=max(ans,dp[i]); } cout << n-ans; } } namespace sub_full { long long t[N],b[N],dp[N],g[N],m; void update(int x,ll v) { for(;x<=m;x+=x&-x) t[x]=max(t[x],v); } long long get(int x) { ll res=0; for(;x;x-=x&-x) res=max(res,t[x]); return res; } void solve() { vector<ll>v; for(int i=1;i<=n;i++) { cin >> a[i]; b[i]=a[i]-1LL*k*i; g[i]=b[i]; v.push_back(b[i]); } sort(v.begin(),v.end(),greater<ll>()); v.erase(unique(all(v)),v.end()); m=v.size(); for(int i=1;i<=n;i++) g[i]=lower_bound(v.begin(),v.end(),b[i],greater<ll>())-v.begin()+1; ll ans=0; for(int i=1;i<=n;i++) { if(b[i]<=0) dp[i]=1; ll cur=get(g[i]); if(cur) dp[i]=max(dp[i],cur+1); ans=max(ans,dp[i]); update(g[i],dp[i]); } cout << n-ans; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin >> n >> k; if(n<=20) sub1::solve(); else if(n<=5000) sub23::solve(); else sub_full::solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...