oj.uz

Submission #91314

# Submission time Handle Problem Language Result Execution time Memory
91314 2018-12-27T05:04:07 Z Aydarov03 K blocks (IZhO14_blocks) C++14
0 / 100
 1000 ms 263168 KB 
#include <bits/stdc++.h>
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;



string ola( int a )
{
    string s = "";
    while(a > 0)s += a % 10 + '0' , a /= 10;

    reverse(s.begin() , s.end());
    return s;
}


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 0;

    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();
    }

}



int 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: In function 'int main()':
blocks.cpp:90: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 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 2 ms 428 KB Output is correct
7 Correct 2 ms 488 KB Output is correct
8 Correct 2 ms 488 KB Output is correct
9 Incorrect 2 ms 572 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 572 KB Output is correct
2 Correct 2 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 612 KB Output is correct
6 Correct 2 ms 612 KB Output is correct
7 Correct 2 ms 612 KB Output is correct
8 Correct 3 ms 624 KB Output is correct
9 Incorrect 2 ms 624 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 1084 ms 672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

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