oj.uz

Submission #171930

# Submission time Handle Problem Language Result Execution time Memory
171930 2019-12-30T16:20:20 Z DeD_TihoN K blocks (IZhO14_blocks) C++14
0 / 100
 23 ms 7720 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< pair<int,int>,int > >c;
        c.pb({{inf,inf},0});
        dp1[0]=inf;
        for (int i=1;i<=n;++i){
            c.pb({{0,dp[i-1]},i});
            int cur=inf;
            int r=i;
            while(a[i]>=c.back().ff.ff){
                int pos=c.back().ss;
                int res=c.back().ff.ss;
                res+=a[i]-c.back().ff.ff;
                cur=min(cur,res);
                c.pop_back();
                r=pos;
            }
            int l=min(cur,c.back().ff.ss);
            dp1[i]=l;
            c.pb({{a[i],cur},r});
        }
        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
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 8 ms 6648 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Incorrect 8 ms 6648 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
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 7 ms 6648 KB Output is correct
8 Correct 7 ms 6648 KB Output is correct
9 Correct 7 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 8 ms 6648 KB Output is correct
13 Correct 9 ms 6648 KB Output is correct
14 Correct 11 ms 6648 KB Output is correct
15 Correct 10 ms 6648 KB Output is correct
16 Incorrect 12 ms 6660 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 6648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 6776 KB Output is correct
2 Correct 8 ms 1016 KB Output is correct
3 Incorrect 22 ms 7720 KB Output isn't correct
4 Halted 0 ms 0 KB -