oj.uz

Submission #171927

# Submission time Handle Problem Language Result Execution time Memory
171927 2019-12-30T16:08:31 Z DeD_TihoN K blocks (IZhO14_blocks) C++14
53 / 100
 1000 ms 7800 KB 
#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ll long long
#define ld long double
#define endl '\n'
#define all(a) a.begin(),a.end()
#define ull unsigned long long
#define y1 yaumru
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define iter set< pair<int,int> >::iterator
#define iter1 set< pair< int,pair<int,int> > >::iterator
#define int long long
using namespace std;
using namespace __gnu_pbds;

template<class T>
using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
using ordered_multiset=tree<T,null_type,less_equal<T>,rb_tree_tag,tree_order_statistics_node_update>;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd1(chrono::steady_clock::now().time_since_epoch().count());

//find_by_order
//order_of_key

const int N=1e5+7;
const int inf=1e18+1e9;
const int mod=1e9+7;
const ld eps=1e-9;

int a[N];
int dp[N];
int dp1[N];
int t[N*4];
int ob[N*4];

void push(int v,int l,int r)
{
    if (ob[v]){
        t[v]+=ob[v];
        if (l!=r){
            ob[v+v]+=ob[v];
            ob[v+v+1]+=ob[v];
        }
        ob[v]=0;
    }
}

void update(int v,int l,int r,int l1,int r1,int x)
{
    push(v,l,r);
    if (l>r1 || r<l1)return;
    if (l>=l1 && r<=r1){
        ob[v]+=x;
        push(v,l,r);
        return;
    }
    int mid=(l+r)/2;
    update(v+v,l,mid,l1,r1,x);
    update(v+v+1,mid+1,r,l1,r1,x);
    t[v]=min(t[v+v],t[v+v+1]);
}

int get(int v,int l,int r,int l1,int r1)
{
    push(v,l,r);
    if (l>r1 || r<l1)return inf;
    if (l>=l1 && r<=r1){
        return t[v];
    }
    int mid=(l+r)/2;
    return min(get(v+v,l,mid,l1,r1),get(v+v+1,mid+1,r,l1,r1));
}

main ()
{
    ios;
    int n,k;
    cin>>n>>k;
    for (int i=1;i<=n;++i){
        cin>>a[i];
    }
    int mx=0;
    dp[0]=inf;
    for (int i=1;i<=n;++i){
        mx=max(mx,a[i]);
        dp[i]=mx;
    }
    for (int tt=2;tt<=k;++tt){
        fill(t,t+N*4,0);
        fill(ob,ob+N*4,0);
        vector< pair<int,int> >c;
        c.pb({inf,0});
        dp1[0]=inf;
        for (int i=1;i<=n;++i){
            update(1,1,n,i,i,dp[i-1]);
            c.pb({0,i});
            int r=i;
            while(a[i]>c.back().ff){
                int pos=c.back().ss;
                update(1,1,n,pos,r,a[i]-c.back().ff);
                c.pop_back();
                r=pos-1;
            }
            c.pb({a[i],r+1});
            dp1[i]=get(1,1,n,1,i);
        }
        for (int i=0;i<=n;++i){
            dp[i]=dp1[i];
        }
    }
    cout<<dp[n]<<endl;
}

Compilation message

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 7 ms 6648 KB Output is correct
5 Correct 7 ms 6648 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 7 ms 6648 KB Output is correct
8 Correct 7 ms 6648 KB Output is correct
9 Correct 8 ms 6648 KB Output is correct
10 Correct 8 ms 6648 KB Output is correct
11 Correct 9 ms 6620 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 8 ms 6652 KB Output is correct
14 Correct 8 ms 6652 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 9 ms 6648 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 9 ms 6692 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 6776 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 404 KB Output is correct
5 Correct 7 ms 6648 KB Output is correct
6 Correct 7 ms 6648 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 7 ms 6648 KB Output is correct
9 Correct 7 ms 6648 KB Output is correct
10 Correct 7 ms 6648 KB Output is correct
11 Correct 8 ms 6648 KB Output is correct
12 Correct 8 ms 6648 KB Output is correct
13 Correct 16 ms 6776 KB Output is correct
14 Correct 16 ms 6648 KB Output is correct
15 Correct 42 ms 6648 KB Output is correct
16 Correct 41 ms 6648 KB Output is correct
17 Correct 26 ms 6780 KB Output is correct
18 Correct 41 ms 6648 KB Output is correct
19 Correct 42 ms 6648 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 6908 KB Output is correct
2 Correct 7 ms 1016 KB Output is correct
3 Correct 200 ms 7800 KB Output is correct
4 Execution timed out 1067 ms 7672 KB Time limit exceeded
5 Halted 0 ms 0 KB -