oj.uz

Submission #91362

# Submission time Handle Problem Language Result Execution time Memory
91362 2018-12-27T08:58:09 Z Aydarov03 K blocks (IZhO14_blocks) C++14
18 / 100
 1000 ms 980 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005;
const int inf = 1e9+7;
int a[N];
int tree[N * 4];
int  n , k , cnt;
int ans = INT_MAX;



void upd( int pos , int val , int v = 1 , int tl = 1 , int tr = n )
{
    if(tl == tr)
    {
        tree[v] = val;
        return;
    }

    int mid = (tl + tr) / 2;

    if( pos <= mid )
        upd(pos , val , v + v , tl , mid );
    else
        upd(pos , val , v+v+1 ,mid+1, tr );

    tree[v] = max( tree[v+v] , tree[v+v+1] );
}


int get( int l , int r , int v = 1 , int tl = 1 , int tr = n )
{
    if(tl > r || tr < l)
        return -1;

    if( l <= tl && tr <= r )
        return tree[v];

    int mid = (tl + tr) / 2;

    return max( get(l , r , v + v , tl , mid)  , get(l , r , v+v+1 ,mid+1 ,tr) );
}

void rec( int ost = n , int id = 1 , vector<int> v = {})
{
    if( id == k && ost )
    {
        v.push_back( ost );
//        for(auto c : v)cout << c << " ";cout << endl;
        int ls = 0 , cnt = 0;
        bool z = 0;
        for(auto c : v)
        {
            if(cnt > ans)return;
            cnt += get(ls , ls + c - z );
            ls = ls + c + 1 - z;
            z = 1;

        }

        ans = min(ans , cnt);
        return;
    }

    if( ost >= (k - id) )
    for(int i = 1; i <= ost; i++)
    {
        v.push_back(i);
        rec( ost - i , id + 1 , v);
        v.pop_back();
    }

}



main()
{

    cin >> n >> k;

    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
        upd(i , a[i]);
    }

    rec();

    cout << ans;


}
/*
5 2
1 2 3 4 5

*/

Compilation message

blocks.cpp:78:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 476 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 2 ms 516 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Correct 2 ms 644 KB Output is correct
12 Correct 2 ms 644 KB Output is correct
13 Correct 906 ms 736 KB Output is correct
14 Execution timed out 1080 ms 736 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 736 KB Output is correct
2 Correct 2 ms 736 KB Output is correct
3 Correct 2 ms 736 KB Output is correct
4 Correct 2 ms 736 KB Output is correct
5 Correct 2 ms 736 KB Output is correct
6 Correct 2 ms 736 KB Output is correct
7 Correct 2 ms 736 KB Output is correct
8 Correct 2 ms 736 KB Output is correct
9 Correct 2 ms 736 KB Output is correct
10 Correct 2 ms 736 KB Output is correct
11 Correct 2 ms 736 KB Output is correct
12 Correct 2 ms 736 KB Output is correct
13 Correct 2 ms 736 KB Output is correct
14 Correct 55 ms 736 KB Output is correct
15 Correct 55 ms 736 KB Output is correct
16 Correct 22 ms 736 KB Output is correct
17 Correct 22 ms 736 KB Output is correct
18 Correct 55 ms 736 KB Output is correct
19 Correct 22 ms 736 KB Output is correct
20 Correct 2 ms 736 KB Output is correct

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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