Submission #140655

#	Time	Username	Problem	Language	Result	Execution time	Memory
140655		rzbt	K blocks (IZhO14_blocks)	C++14	100 / 100	178 ms	4176 KiB

blocks

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define MAXN 100005
typedef long long ll;


using namespace std;

ll n,k;
ll niz[MAXN];
ll dpp[MAXN],dp[MAXN];
stack<pair<ll,ll> > s;


int main()
{
    scanf("%lld %lld", &n, &k);
    for(ll i=1;i<=n;i++)
        scanf("%lld",niz+i);
    dp[0]=dpp[0]=1e9;
    ll tmax=0;
    for(ll i=1;i<=n;i++){
        tmax=max(tmax,niz[i]);
        dpp[i]=tmax;
    }
    for(ll j=1;j<k;j++){
        //for(ll i=1;i<=n;i++)printf("    %d\n",dpp[i]);
        //printf("\n\n\n");
        for(ll i=1;i<=n;i++){
            ll tS = dpp[i-1];
            while(!s.empty() && niz[s.top().F] < niz[i]){
                tS=min(tS,s.top().S);
                s.pop();
            }
            if(!s.empty())dp[i]=min(dp[s.top().F],niz[i]+tS);
            else dp[i]=niz[i]+tS;
            s.push(mp(i,tS));
        }
        for(ll i=1;i<=n;i++)dpp[i]=dp[i];
        while(!s.empty())s.pop();
    }
    printf("%lld",dpp[n]);
    return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
blocks.cpp:23:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",niz+i);
         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 47 / 47