Submission #757595

#	Time	Username	Problem	Language	Result	Execution time	Memory
757595		Fidan	K blocks (IZhO14_blocks)	C++17	100 / 100	777 ms	6408 KiB

blocks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for(ll i=ll(a); i<ll(b); i++)
#define repn(i, a, b) for(ll i=ll(b)-1; i>=ll(a); i--)
#define pb push_back
#define si size()
#define ff first
#define ss second
#define be begin()
#define en end()
const ll N=(1e5)+1;
const ll K=101;
const ll inf=(1e8)+1;
vector<ll> v(N);
vector<ll> x(N, -1);
vector<ll> s;
vector<ll> dp1(N, inf), dp2(N, inf);
vector<ll> T(2*N, inf);
void construct(ll n){
	rep(i, 0, n){
		T[n+i]=v[i];
	}
	repn(i, 1, n){
		T[i]=min(T[2*i], T[2*i+1]);
	}
}
void upd(ll in, ll val, ll n){
	in+=n;
	T[in]=val;
	while(in>1){
		in/=2;
		T[in]=min(T[2*in], T[2*in+1]);
	}
}
ll que(ll l, ll r, ll n){
	l+=n, r+=n;
	ll mn=inf;
	while(l<r){
		if(l%2==1){
			mn=min(mn, T[l]);
			l++;
		}
		if(r%2==1){
			r--;
			mn=min(mn, T[r]);
		}
		l/=2;
		r/=2;
	}
	return mn;
}
void solve(){
	ll n, k;
	cin>>n>>k;
	rep(i, 0, n){
		cin>>v[i];
	}
	ll o=0;
	s.pb(1);
	rep(i, 1, n){
		if(v[s[o]]>=v[i]){
			x[i]=s[o];
		}
		else{
			while(true){
				if(o<0) break;
				if(v[s[o]]>=v[i]) break;
				s.pop_back();
				o--;
			}
			if(o!=-1){
				x[i]=s[o];
			}
		}
		o++;
		s.pb(i);
	}
	dp1[0]=v[0];
	upd(0, dp1[0], n);
	rep(i, 1, n){
		dp1[i]=max(dp1[i-1], v[i]);
		upd(i, dp1[i], n);
	}
	rep(j, 2, k+1){
		rep(i, 0, n){
			dp2[i]=inf;
			if(i+1<j){
				continue;
			}
			else{
				dp2[i]=v[i]+dp1[i-1];
				if(x[i]==-1){
					dp2[i]=min(dp2[i], v[i]+que(0, i-1, n));
				}
				else if(x[i]==i-1){
					dp2[i]=min(dp2[i], dp2[x[i]]);
				}
				else{
					dp2[i]=min(dp2[i], v[i]+que(x[i]+1, i-1, n));
					dp2[i]=min(dp2[i], dp2[x[i]]);
				}
			}
		}
		rep(i, 0, n){
			upd(i, dp2[i], n);
		}
		swap(dp1, dp2);
	}
	cout<<dp1[n-1];
}
int main(){
	ios_base::sync_with_stdio();
	cin.tie(0);
	ll t=1;
	//~ cin>>t;
	while(t--){
		solve();
	}
	return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47