Submission #91350

#	Time	Username	Problem	Language	Result	Execution time	Memory
91350		Aydarov03	K blocks (IZhO14_blocks)	C++14	0 / 100	1081 ms	964 KiB

blocks

#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 = c + 1;
            z = 1;
        }
        ans = min(ans , cnt);
        return;
    }

    if( ost >= (k - id) )
    for(int i = 1; i <= ost - k + 1; 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++)
    {
        scanf("%d" , &a[i]);
        upd(i , a[i]);
    }

    rec();

    cout << ans;


}
/*
5 2
1 2 3 4 5

*/

Compilation message (stderr)

blocks.cpp:77:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
blocks.cpp: In function 'int main()':
blocks.cpp:84:27: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d" , &a[i]);
                      ~~~~~^
blocks.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d" , &a[i]);
         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 18
• Subtask 3: 0 / 21
• Subtask 4: 0 / 47