Submission #1019272

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019272		andrewp	K blocks (IZhO14_blocks)	C++17	53 / 100	1073 ms	39516 KiB

blocks

//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array
#define DBG(x) cout << #x << "= " << x << "\n"

const int mxN=1e5;
const ll inf=(ll)(1e18);
int n, k, a[mxN];
ll dp[mxN][105];

int main() {
//	ios::sync_with_stdio(0);
//	cin.tie(0);

    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
    for(int i=0; i<=n; ++i) {
        for(int j=0; j<=k; ++j) dp[i][j]=inf;
    }
    int mx=a[1];
    for(int i=1; i<=n; ++i) {
        mx=max(mx, a[i]);
        dp[i][1]=mx;
    }
    for(int j=2; j<=k; ++j) {
        stack<ar<ll, 2>> stk;
        for(int i=1; i<=n; ++i) {
            ll upd=dp[i-1][j-1];
            while((!stk.empty())&&(stk.top()[0]<a[i])) {
                upd=min(upd, stk.top()[1]);
                stk.pop();
            }
            if(stk.empty() || (a[i]+upd<stk.top()[0]+stk.top()[1])) {
                stk.push({a[i], upd});
            }
            if(j>i) continue;
            dp[i][j]=stk.top()[0]+stk.top()[1];
        }
    }
    printf("%lld\n", dp[n][k]);
	return 0;
}

Compilation message (stderr)

blocks.cpp: In function 'int main()':
blocks.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
blocks.cpp:19:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
      |                             ~~~~~^~~~~~~~~~~~~

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