Submission #1270121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270121		WH8	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	145 ms	17616 KiB

triusis

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

#define int long long 
#define pll pair<int, int>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'

signed main(){
	int n,m;cin>>n>>m;
	set<pair<int,int>> s;
	vector<int> dp0(n+1, 1e9), v(n+1, 0), dp1(n+1, 1e9);
	dp0[0]=0,dp1[0]=0;
	for(int i=1;i<=n;i++)cin>>v[i];
	s.insert({0, 0});
	int mn=0;
	for(int i=1;i<=n;i++){
		pair<int,int> q={v[i]-i*m, -1e15};
		auto it=s.lower_bound(q);
		int cand=1e15;
		//~ printf("q.f %lld\n", q.f);
		//~ for(auto it:s)cout<<"( "<<it.f<<" "<<it.s<<" ) "<<endl;
		if(it!=s.end()){
			cand=min(cand, i-1+(*it).s);
			//~ printf("%lld <-- cand\n", cand);
			
			auto d=s.upper_bound(q);
			while(d != s.begin() and (*prev(d)).s >= cand-i){
				s.erase(prev(d));
			}
			
			pair<int,int> u={v[i]-i*m, cand-i};
			s.insert(u);
		}
		dp0[i]=cand;
		dp1[i]=mn+i;
		mn=min(mn, dp0[i]-i);
		//~ printf("i %lld, dp0 %lld dp1 %lld\n", i, dp0[i], dp1[i]);
	}
	cout<<min(dp0[n], dp1[n]);
}

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