oj.uz

Submission #688611

# Submission time Handle Problem Language Result Execution time Memory
688611 2023-01-27T20:47:28 Z luka1234 K blocks (IZhO14_blocks) C++14
0 / 100
 24 ms 39860 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;
int n,m;
int a[100001];
int dp[100001][101];
int t[101][400001];
int marc[100001];
void update(int v,int tl,int tr,int pos,int x,int ind){
	if(tl==tr){
		t[ind][v]=x;
	}
	else{
		int 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]);
	}
}
int get(int v,int tl,int tr,int l,int r,int ind){
	if(r<tl||l>tr){
		return 1e9;
	}
	if(l>=tl&&r<=tr){
		return t[ind][v];
	}
	int m=(tl+tr)/2;
	int f1=get(2*v,tl,m,l,r,ind);
	int f2=get(2*v+1,m+1,tr,l,r,ind);
	int f=min(f1,f2);
	return f;
}
void make(){
	stack<int> st;
	for(int k=n;k>=1;k--){
		while(!st.empty()&&a[k]>a[st.top()]){
			marc[st.top()]=k;
			st.pop();
		}
		st.push(k);
	}
}
int main(){
	for(int i=0;i<=100000;i++){
		for(int j=0;j<=100;j++){
			dp[i][j]=1e9;
		}
	}
	cin>>n>>m;
	int mx=0;
	for(int 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(int k=2;k<=m;k++){
		for(int i=k;i<=n;i++){
			int f=marc[i];
			int mn=get(1,1,n,f+1,i,k-1);
			mn=mn+a[i];
			int f1=dp[f][k];
			mn=min(mn,f1);
			dp[i][k]=mn;
			update(1,1,n,i,mn,k);
		}
	}
	cout<<dp[n][m];
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 39764 KB Output is correct
2 Correct 22 ms 39820 KB Output is correct
3 Correct 21 ms 39844 KB Output is correct
4 Correct 21 ms 39764 KB Output is correct
5 Correct 21 ms 39764 KB Output is correct
6 Correct 21 ms 39764 KB Output is correct
7 Correct 21 ms 39764 KB Output is correct
8 Correct 19 ms 39836 KB Output is correct
9 Incorrect 21 ms 39764 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 39840 KB Output is correct
2 Correct 21 ms 39752 KB Output is correct
3 Correct 22 ms 39728 KB Output is correct
4 Correct 24 ms 39752 KB Output is correct
5 Correct 23 ms 39784 KB Output is correct
6 Correct 22 ms 39812 KB Output is correct
7 Correct 21 ms 39796 KB Output is correct
8 Correct 22 ms 39860 KB Output is correct
9 Incorrect 21 ms 39764 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 39764 KB Output is correct
2 Correct 22 ms 39820 KB Output is correct
3 Correct 21 ms 39844 KB Output is correct
4 Correct 21 ms 39764 KB Output is correct
5 Correct 21 ms 39764 KB Output is correct
6 Correct 21 ms 39764 KB Output is correct
7 Correct 21 ms 39764 KB Output is correct
8 Correct 19 ms 39836 KB Output is correct
9 Incorrect 21 ms 39764 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 39764 KB Output is correct
2 Correct 22 ms 39820 KB Output is correct
3 Correct 21 ms 39844 KB Output is correct
4 Correct 21 ms 39764 KB Output is correct
5 Correct 21 ms 39764 KB Output is correct
6 Correct 21 ms 39764 KB Output is correct
7 Correct 21 ms 39764 KB Output is correct
8 Correct 19 ms 39836 KB Output is correct
9 Incorrect 21 ms 39764 KB Output isn't correct
10 Halted 0 ms 0 KB -