oj.uz

답안 #171929

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171929 2019-12-30T16:18:24 Z DeD_TihoN K개의 묶음 (IZhO14_blocks) C++14
0 / 100
 23 ms 7744 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

# 결과 실행 시간 메모리 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 8 ms 6648 KB Output is correct
6 Correct 2 ms 380 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

# 결과 실행 시간 메모리 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 8 ms 6648 KB Output is correct
5 Correct 8 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 9 ms 6648 KB Output is correct
13 Correct 9 ms 6652 KB Output is correct
14 Correct 10 ms 6648 KB Output is correct
15 Correct 10 ms 6648 KB Output is correct
16 Incorrect 12 ms 6648 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 23 ms 6648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 6776 KB Output is correct
2 Correct 7 ms 1016 KB Output is correct
3 Incorrect 21 ms 7744 KB Output isn't correct
4 Halted 0 ms 0 KB -