oj.uz

Submission #140654

# Submission time Handle Problem Language Result Execution time Memory
140654 2019-08-04T09:24:34 Z rzbt K blocks (IZhO14_blocks) C++14
0 / 100
 7 ms 632 KB 
#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++){
            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];
    }
    printf("%lld",dpp[n]);
    return 0;
}

Compilation message

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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Incorrect 2 ms 376 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Incorrect 2 ms 376 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

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

Subtask #4
0 / 47.0

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