Submission #1126869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126869		_rain_	K blocks (IZhO14_blocks)	C++20	100 / 100	144 ms	160864 KiB

blocks

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
#define inp(data_name) freopen(data_name,"r",stdin);
#define out(data_name) freopen(data_name,"w",stdout);
#define name "main"
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(b);i>=(a);--i)

#define N 1'000'00
#define MAXK 1'00
const LL INF=(LL)1e9+7;
int a[N+2],n,k;
LL dp[N+2][MAXK+2]={},f[N+2][MAXK+2]={};

int32_t main(){
    scanf("%d%d",&n,&k);
    FOR(i,1,n) scanf("%d",&a[i]);
    vector<int>q;
    a[0]=INF;q.push_back(0);
    memset(dp,0x3f,sizeof dp);
    memset(f,0x3f,sizeof f);
    dp[0][0]=0;
    FOR(i,1,n){
        while (q.size()&&a[q.back()]<a[i]) {
            FOR(j,1,k) {
                f[i][j]=min(f[q.back()][j],f[i][j]);
                dp[i][j]=min(f[q.back()][j-1]+a[i],dp[i][j]);
            }
            q.pop_back();
        }
        int x=q.back();
        FOR(j,1,k){
            dp[i][j]=min({dp[i][j],dp[x][j],dp[x][j-1]+a[i]});
            f[i][j]=min(f[i][j],dp[i][j]);
        }
        q.push_back(i);
    }
    printf("%lld",dp[n][k]);
}

Compilation message (stderr)

blocks.cpp: In function 'int32_t 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:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     FOR(i,1,n) scanf("%d",&a[i]);
      |                ~~~~~^~~~~~~~~~~~

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