| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1101516 | quocthang | K blocks (IZhO14_blocks) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define base 31
#define fi first
#define endl "\n"
#define se second
#define NAME "FILE"
#define ll long long
//#define int long long
#define mod 1000000007
#define pii pair<int,int>
#define bit(mask,i) (mask&(1<<i))
#define lcm(a,b) ((a*b)/__gcd(a,b))
#define turn_on(mask,i) (mask|(1<<i))
#define turn_off(mask,i) (mask^(1<<i))
template <class T1, class T2>
bool maximize(T1 &a, T2 b){if (a < b){a = b; return 1;} return 0;}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){if (a > b){a = b; return 1;} return 0;}
template <class T1, class T2>
void add(T1 &a, T2 b){a += b; if (a >= mod) a -= mod;}
template <class T1, class T2>
void sub(T1 &a, T2 b){a -= b; if (a < 0) a += mod;}
using namespace std;
int n,k,a[100010];
int mn[100010][20],l[1000010];
stack<int>st;
int get(int l,int r){
int k=__lg(r-l+1);
return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
if (fopen(NAME".inp","r")){
freopen(NAME".inp","r",stdin);
freopen(NAME".out","w",stdout);
}
cin>>n>>k;
int dp[n+10][k+10];
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=n;i++){
while(st.size()&&a[st.top()]<=a[i]) st.pop();
if(st.size())l[i]=st.top();else l[i]=0;
}
memset(dp,0x3f,sizeof dp);
dp[0][0]=0;
for(int j=1;j<=k;j++){
for(int i=0;i<=n;i++)mn[i][0]=dp[i][j-1];
for(int j=1;(1<<j)<=n+1;j++){
for(int i=0;i+(1<<j)-1<=n;i++){
mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
}
}
for(int i=1;i<=n;i++){
minimize(dp[i][j],get(l[i],i-1)+a[i]);
minimize(dp[i][j],dp[l[i]][j]);
}
}
cout<<dp[n][k];
}
-