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 ll long long
#define ldb long double
#define endl '\n'
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ForD(i,r,l) for(int i=r;i>=l;i--)
#define REP(i,l,r) For(i,l,r-1)
#define PER(i,r,l) ForD(i,r-1,l)
#define ff first
#define ss second
#define pb emplace_back
#define all(x) x.begin(),x.end()
#define All(x,n) x+1,x+1+n
#define Alll(x,n) x,x+n
#define sz(x) (signed)x.size()
#define unq(x) x.resize(unique(all(x))-x.begin())
#define mpa make_pair
#ifdef NCGM
#include"debug.h"
#else
#define debug(...) "fr";
#endif
using namespace std;
const int N=1e5+3;
const ll INF=1e17;
int n,k,op[N][103],a[N],st[N][20];
ll f[N][103];
void pre() {
For(i,1,n) st[i][0]=a[i];
for(int j=1;j<=16;j++)
for(int i=1;i+(1<<j)-1<=n;i++) st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
}
int get(int l,int r) {
int len=__lg(r-l+1);
return max(st[l][len],st[r-(1<<len)+1][len]);
}
void solve(int k,int l,int r,int lo,int hi) {
if (l>r) return;
int mid=l+r>>1;
if (mid<k) {
solve(k,mid+1,r,lo,hi);
return;
}
pair<ll,int> optimal={INF,-1};
For(i,lo,min(mid,hi)) optimal=min(optimal,mpa(f[i-1][k-1]+get(i,mid),i));
f[mid][k]=optimal.ff;
solve(k,l,mid-1,lo,optimal.ss);
solve(k,mid+1,r,optimal.ss,hi);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
For(i,1,n) cin >> a[i];
pre();
For(i,0,k)
For(j,0,n) f[j][i]=INF;
f[0][0]=0;
For(i,1,k) solve(i,1,n,1,n);
cout << f[n][k];
return 0;
}
Compilation message (stderr)
blocks.cpp: In function 'void pre()':
blocks.cpp:35:74: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
35 | for(int i=1;i+(1<<j)-1<=n;i++) st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]);
| ~^~
blocks.cpp: In function 'void solve(int, int, int, int, int)':
blocks.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid=l+r>>1;
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |