oj.uz

Submission #91350

# Submission time Handle Problem Language Result Execution time Memory
91350 2018-12-27T08:31:17 Z Aydarov03 K blocks (IZhO14_blocks) C++14
0 / 100
 1000 ms 964 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 = 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

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.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 532 KB Output is correct
4 Correct 2 ms 532 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 ms 532 KB Output is correct
7 Correct 2 ms 532 KB Output is correct
8 Correct 2 ms 656 KB Output is correct
9 Incorrect 2 ms 724 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 2 ms 784 KB Output is correct
6 Correct 2 ms 784 KB Output is correct
7 Correct 2 ms 784 KB Output is correct
8 Correct 2 ms 784 KB Output is correct
9 Incorrect 2 ms 784 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 784 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 1081 ms 964 KB Time limit exceeded
2 Halted 0 ms 0 KB -