Submission #1079023

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079023		beobuoibacky	K blocks (IZhO14_blocks)	C++14	100 / 100	237 ms	82304 KiB

blocks

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+210;
int dp[N][102], p[N];
int n, k;
int32_t main(){
    #define task "task"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    memset(dp, 63, sizeof dp);
    for(int i=1;i<=n;i++)cin >> p[i];
    for(int i=1;i<=n;i++){
      if(i==1) dp[i][1]=p[i];
      else dp[i][1]=max(dp[i-1][1],p[i]);
    }
    for(int j=2;j<=k;j++){
        stack<int> st;
        while(!st.empty()) st.pop();
        for(int i=1;i<=n;i++){
            while(st.size() and p[i]>=p[st.top()]){
                dp[i][j]=min(dp[i][j], min(dp[st.top()][j-1]+p[i], dp[st.top()][j]-p[st.top()]+p[i]));
               // cerr << dp[i][j] << " " << i << " " << j << " " << "\n";
               st.pop();
            }
            if(st.size()){
              dp[i][j]=min(min(dp[st.top()][j-1]+p[i], dp[st.top()][j]), dp[i][j]);
            }
            st.push(i);
        }
      }
      cout << dp[n][k];
}

Compilation message (stderr)

blocks.cpp: In function 'int32_t main()':
blocks.cpp:10:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
blocks.cpp:11:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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