제출 #1197426

#제출 시각아이디문제언어결과실행 시간메모리
1197426huygdK blocks (IZhO14_blocks)C++20
53 / 100
1096 ms4420 KiB
#include <bits/stdc++.h> #pragma GCC optimize ("O3,unroll-loops") using namespace std; int n,k; int a[100001]; int st[400001]; int dp[100001][101]; void upd(int id,int l,int r,int i,int v) { if (l>i||r<i) return; if (l==r) { st[id]=v; return; } int mid=(l+r)>>1; upd(id<<1,l,mid,i,v); upd(id<<1|1,mid+1,r,i,v); st[id]=max(st[id<<1],st[id<<1|1]); } int get(int id,int l,int r,int u,int v) { if (l>v||r<u) return 0; if (l>=u&&r<=v) return st[id]; int mid=(l+r)>>1; return max(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v)); } int F(int x,int y) { if (dp[x][y]) return dp[x][y]; if (y==k-1) return dp[x][y]=get(1,1,n,x,n); dp[x][y]=1e9; for (int i=x;i<=n+1-(k-y);++i) dp[x][y]=min(dp[x][y],get(1,1,n,x,i)+F(i+1,y+1)); return dp[x][y]; } int main() { cin.tie(0)->ios_base::sync_with_stdio(0); cin>>n>>k; for (int i=1;i<=n;++i) { cin>>a[i]; upd(1,1,n,i,a[i]); } cout<<F(1,0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...