oj.uz

Submission #88511

# Submission time Handle Problem Language Result Execution time Memory
88511 2018-12-06T08:55:16 Z ABCD K blocks (IZhO14_blocks) C++14
53 / 100
 1000 ms 1592 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);
         ^

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 552 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 2 ms 608 KB Output is correct
9 Correct 2 ms 672 KB Output is correct
10 Correct 2 ms 680 KB Output is correct
11 Correct 2 ms 812 KB Output is correct
12 Correct 2 ms 812 KB Output is correct
13 Correct 4 ms 812 KB Output is correct
14 Correct 4 ms 812 KB Output is correct
15 Correct 2 ms 812 KB Output is correct
16 Correct 3 ms 812 KB Output is correct
17 Correct 2 ms 812 KB Output is correct
18 Correct 4 ms 812 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 812 KB Output is correct
2 Correct 2 ms 812 KB Output is correct
3 Correct 2 ms 816 KB Output is correct
4 Correct 2 ms 820 KB Output is correct
5 Correct 2 ms 824 KB Output is correct
6 Correct 2 ms 828 KB Output is correct
7 Correct 2 ms 836 KB Output is correct
8 Correct 2 ms 836 KB Output is correct
9 Correct 2 ms 932 KB Output is correct
10 Correct 2 ms 932 KB Output is correct
11 Correct 2 ms 932 KB Output is correct
12 Correct 2 ms 932 KB Output is correct
13 Correct 2 ms 932 KB Output is correct
14 Correct 2 ms 932 KB Output is correct
15 Correct 2 ms 932 KB Output is correct
16 Correct 2 ms 932 KB Output is correct
17 Correct 2 ms 932 KB Output is correct
18 Correct 3 ms 932 KB Output is correct
19 Correct 2 ms 932 KB Output is correct
20 Correct 2 ms 932 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 932 KB Output is correct
2 Correct 2 ms 932 KB Output is correct
3 Correct 2 ms 932 KB Output is correct
4 Correct 2 ms 932 KB Output is correct
5 Correct 2 ms 932 KB Output is correct
6 Correct 2 ms 932 KB Output is correct
7 Correct 2 ms 932 KB Output is correct
8 Correct 2 ms 932 KB Output is correct
9 Correct 2 ms 952 KB Output is correct
10 Correct 2 ms 956 KB Output is correct
11 Correct 2 ms 960 KB Output is correct
12 Correct 2 ms 964 KB Output is correct
13 Correct 9 ms 972 KB Output is correct
14 Correct 9 ms 1104 KB Output is correct
15 Correct 2 ms 1104 KB Output is correct
16 Correct 2 ms 1104 KB Output is correct
17 Correct 8 ms 1104 KB Output is correct
18 Correct 2 ms 1104 KB Output is correct
19 Correct 2 ms 1104 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 1592 KB Time limit exceeded
2 Halted 0 ms 0 KB -