oj.uz

Submission #688620

# Submission time Handle Problem Language Result Execution time Memory
688620 2023-01-27T21:06:18 Z luka1234 K blocks (IZhO14_blocks) C++14
0 / 100
 39 ms 79372 KB 
#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
ll n,m;
ll a[100001];
ll dp[100001][101];
ll t[101][400001];
ll marc[100001];
void update(ll v,ll tl,ll tr,ll pos,ll x,ll ind){
	if(tl==tr){
		t[ind][v]=x;
	}
	else{
		ll m=(tl+tr)/2;
		if(pos<=m){
			update(2*v,tl,m,pos,x,ind);
		}
		else{
			update(2*v+1,m+1,tr,pos,x,ind);
		}
		t[ind][v]=min(t[ind][2*v],t[ind][2*v+1]);
	}
}
ll get(ll v,ll tl,ll tr,ll l,ll r,ll ind){
	if(r<tl||l>tr){
		return 1e18;
	}
	if(l>=tl&&r<=tr){
		return t[ind][v];
	}
	ll m=(tl+tr)/2;
	ll f1=get(2*v,tl,m,l,r,ind);
	ll f2=get(2*v+1,m+1,tr,l,r,ind);
	ll f=min(f1,f2);
	return f;
}
void make(){
	stack<ll> st;
	for(ll k=n;k>=1;k--){
		while(!st.empty()&&a[k]>a[st.top()]){
			int f=a[st.top()];
			marc[st.top()]=k;
			st.pop();
		}
		st.push(k);
	}
}
int main(){
	for(ll i=0;i<=100000;i++){
		for(ll j=0;j<=100;j++){
			dp[i][j]=1e18;
		}
	}
	cin>>n>>m;
	ll mx=0;
	for(ll k=1;k<=n;k++){
		cin>>a[k];
		mx=max(mx,a[k]);
		dp[k][1]=mx;
		update(1,1,n,k,mx,1);
	}
	make();
	for(ll k=2;k<=m;k++){
		for(ll i=k;i<=n;i++){
			ll f=marc[i];
			ll mn1=dp[i-1][k-1]+a[i];
			if(f==i-1){
				ll mn=dp[i-1][k];
				mn=min(mn,mn1);
				dp[i][k]=mn;
				update(1,1,n,i,mn,k);
				continue;
			}
			ll mn=get(1,1,n,f+1,i-1,k-1);
			mn=mn+a[i];
			ll f1=dp[f][k];
			mn=min(mn,f1);
			mn=min(mn,mn1);
			dp[i][k]=mn;
			update(1,1,n,i,mn,k);
		}
	}
	cout<<dp[n][m];
    return 0;
}

Compilation message

blocks.cpp: In function 'void make()':
blocks.cpp:48:8: warning: unused variable 'f' [-Wunused-variable]
   48 |    int f=a[st.top()];
      |        ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 79316 KB Output is correct
2 Correct 39 ms 79272 KB Output is correct
3 Correct 33 ms 79292 KB Output is correct
4 Correct 38 ms 79360 KB Output is correct
5 Correct 33 ms 79372 KB Output is correct
6 Correct 33 ms 79308 KB Output is correct
7 Correct 32 ms 79336 KB Output is correct
8 Correct 34 ms 79316 KB Output is correct
9 Incorrect 39 ms 79260 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 79308 KB Output is correct
2 Correct 33 ms 79296 KB Output is correct
3 Correct 33 ms 79372 KB Output is correct
4 Correct 33 ms 79316 KB Output is correct
5 Correct 33 ms 79336 KB Output is correct
6 Correct 34 ms 79248 KB Output is correct
7 Correct 34 ms 79248 KB Output is correct
8 Correct 33 ms 79292 KB Output is correct
9 Incorrect 34 ms 79292 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 79316 KB Output is correct
2 Correct 39 ms 79272 KB Output is correct
3 Correct 33 ms 79292 KB Output is correct
4 Correct 38 ms 79360 KB Output is correct
5 Correct 33 ms 79372 KB Output is correct
6 Correct 33 ms 79308 KB Output is correct
7 Correct 32 ms 79336 KB Output is correct
8 Correct 34 ms 79316 KB Output is correct
9 Incorrect 39 ms 79260 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 79316 KB Output is correct
2 Correct 39 ms 79272 KB Output is correct
3 Correct 33 ms 79292 KB Output is correct
4 Correct 38 ms 79360 KB Output is correct
5 Correct 33 ms 79372 KB Output is correct
6 Correct 33 ms 79308 KB Output is correct
7 Correct 32 ms 79336 KB Output is correct
8 Correct 34 ms 79316 KB Output is correct
9 Incorrect 39 ms 79260 KB Output isn't correct
10 Halted 0 ms 0 KB -