oj.uz

Submission #88510

# Submission time Handle Problem Language Result Execution time Memory
88510 2018-12-06T08:53:04 Z ABCD K blocks (IZhO14_blocks) C++14
0 / 100
 4 ms 696 KB 
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int N=1e5+5;
const int oo=1e8+5;

int m;
int n,k;
int a[N];
int IT[N*8];
int F[N][105];


void build(int k,int l,int r){
    if(l>r) return;
    if(l==r){
        IT[k]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    IT[k]=max(IT[k*2],IT[k*2+1]);
}

int getmax(int k,int l,int r,int u,int v){
    if(r<u||l>v)
        return 0;
    if(l>=u&&r<=v)
        return IT[k];
    int mid=(l+r)/2;
    return max(getmax(k*2,l,mid,u,v),getmax(k*2+1,mid+1,r,u,v));
}

/*
void Solve(){
    FOR(i,1,k) FOR(j,i,n)
        F[i][j]=F[i-1][j-1]+getmax(1,1,n,j,n);
    cout<<F[k][n];
}*/

int Try(int n,int k){
    if(k==1) return getmax(1,1,m,1,n);
    if(F[n][k]) return F[n][k];
    int tmp=oo+5;
    for(int i=n;i>=max(2,k);i--){
        int t=getmax(1,1,m,i,n);
        tmp=min(tmp,t+Try(i-1,k-1));
    }
    F[n][k]=tmp;
    return F[n][k];
}

main(){
    freopen("blocks.in","r",stdin);
    freopen("blocks.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    FOR(i,1,n) cin>>a[i];
    build(1,1,n);
    m=n;
    int t=Try(n,k);
    cout<<Try(n,k);
}

Compilation message

blocks.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
blocks.cpp: In function 'int main()':
blocks.cpp:64:9: warning: unused variable 't' [-Wunused-variable]
     int t=Try(n,k);
         ^
blocks.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("blocks.in","r",stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:57:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("blocks.out","w",stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 696 KB Output isn't correct
2 Halted 0 ms 0 KB -