oj.uz

Submission #91321

# Submission time Handle Problem Language Result Execution time Memory
91321 2018-12-27T05:44:50 Z Aydarov03 K blocks (IZhO14_blocks) C++14
0 / 100
 1000 ms 263168 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 )
    {
        v.push_back( ost );
        int ls = 0 , cnt = 0;
        bool z = 0;
        for(auto c : v)
        {
            cnt += get(ls , ls + c - z );
            ls = c + 1;
            z = 1;
        }
        ans = min(ans , cnt);

    }

    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:74:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
blocks.cpp: In function 'int main()':
blocks.cpp:81:27: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d" , &a[i]);
                      ~~~~~^
blocks.cpp:81: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 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 444 KB Output is correct
5 Correct 2 ms 508 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 2 ms 508 KB Output is correct
8 Correct 2 ms 524 KB Output is correct
9 Incorrect 2 ms 524 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 524 KB Output is correct
2 Correct 2 ms 524 KB Output is correct
3 Correct 2 ms 584 KB Output is correct
4 Correct 2 ms 584 KB Output is correct
5 Correct 2 ms 584 KB Output is correct
6 Correct 2 ms 584 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Incorrect 2 ms 608 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 1068 ms 608 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Runtime error 212 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -