Submission #334110

#TimeUsernameProblemLanguageResultExecution timeMemory
334110mariamirabella2K blocks (IZhO14_blocks)C++14
0 / 100
1 ms364 KiB
#include <iostream> using namespace std; int rm[100005][20],log2[100005],n,k,a[100005]; long long d[100005][3]; int rmq(int x,int y){ return max(rm[x][log2[y-x+1]],rm[y-(1<<log2[y-x+1])+1][log2[y-x+1]]); } void dve(int j, int st, int dr,int splitl,int splitr) { if(st > dr) return; int mj = (st + dr) >> 1; long long x=(1LL<<50); int splitmj=1; for(int st=splitl;st<=min(splitr,mj);st++){ if(x > d[st][(j+1)%2]+rmq(st+1,mj)) { x=d[st][(j+1)%2]+rmq(st+1,mj); splitmj = st; } } d[mj][j]=x; dve(j,st,mj-1,splitl,splitmj); dve(j,mj+1,dr,splitmj,splitr); } int main() { ///d[i][j]-costul daca impart primele i elemente in j secv cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; } for(int i=1;i<=n;i++){ rm[i][0]=a[i]; } for(int j=1;(1<<j)<=n;j++){ for(int i=1;i<=n-(1<<j)+1;i++){ rm[i][j]= max(rm[i][j-1],rm[i+(1<<(j-1))][j-1]); } } for(int i=2;i<=n;i++){ log2[i]=log2[i/2]+1; } for(int i=1;i<=n;i++){ d[i][1]=max(d[i-1][1],1LL*a[i]); } for(int j=2;j<=k;j++){ dve(j%2,1,n,1,n); } cout<<d[n][k%2]<<'\n'; return 0; }

Compilation message (stderr)

blocks.cpp:4:20: warning: built-in function 'log2' declared as non-function [-Wbuiltin-declaration-mismatch]
    4 | int rm[100005][20],log2[100005],n,k,a[100005];
      |                    ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...